The current research focuses on developing a graph-based method for enumerating all Sudoku squares of rank n. An S-permutation is defined as a permutation that corresponds to an S-permutation matrix. A Sudoku square of rank n has a one-to-one correspondence with a set of mutually disjoint S-permutations derived from \(n^2 \times n^2\) S-permutation matrices. All the S-permutations are generated in the first step, and an S-permutation graph \(G_s = (V_s,E_s)\) is created so that its vertices represent S-permutations, and two vertices are connected by an edge if and only if their corresponding S-permutations are not mutually disjoint. An arbitrary set of mutually disjoint S-permutations is then associated with an independent set of \(G_s\) . A vertex \(v \in V_s\) is chosen at random, and an initiated subgraph \(\hat{G}_s = (\hat{V}_s, \hat{E}_s)\) of \(G_s\) is generated based on all mutually disjoint vertices relative to v. There exists a one-to-one correspondence between the maximal independent set of \(\hat{G}_s\) along with v and the configurations of a Sudoku square. Using this relationship, an algorithm is proposed to count all the maximal independent sets of \(\hat{G}_s\) , which correspond to all possible Sudoku squares of rank n. The correctness of the proposed algorithm is demonstrated. The time complexity of the algorithm is \(O(3^{\frac{\xi _n}{3}})\) , where \(\xi _n\) denotes the total number of S-permutations that are mutually disjoint relative to an S-permutation. The algorithm has been experimentally tested for Sudoku squares of rank up to 3. Additionally, a mathematical expression for the upper bound of the total number of Sudoku squares is provided.
