Sudoku is an interesting number placement puzzle with some simple rules. For some positive integer n, the puzzle involves an n2 × n2 grid partitioned into n2 distinct blocks each of size n × n such that the integers 1 through n2 appear exactly once in each row, each column and each block of the grid. Often some static numbers known as givens are placed according to the difficulty rating in the puzzle and then the rule is to place the numbers from 1 to n2 in the partially filled grid such that the conditions of the puzzle are satisfied. The aim of this paper is to propose a new algorithm for enumerating all possible Sudoku squares of size n2. It is based on the concepts of permutations derived from n2 × n2 S-permutation matrices termed as S-permutations. There is a one-to-one correspondence between Sudoku squares and the set of those S-permutation matrices which are mutually disjoint to each other. The proposed algorithm uses the set of all S-permutations generated by some permutation generation algorithm as input and then enumerates all the subsets of cardinality n2 of all S-permutations which are mutually disjoint to each other. The correctness of the algorithm is established. Its worst-case time complexity is O(wn2 +2logw), where w = (n!)2n. A mathematical formula involving the total number of the sets of (n2-1) mutually disjoint S-permutations is also derived. Experimentally, the proposed algorithm is verified for the Sudoku squares of size 9 × 9. It is observed that our algorithm is more systematic and better in terms of computational efficiency. © 2016 World Scientific Publishing Company.