The New Sudoku Players' Forum

[SianKJones31]

First analysed by B. Felgenhauer and F. Jarvis in 2005 in their paper Enumerating possible Sudoku grids.
They start by first reducing the number of possible grids in a similar way to that explained earlier on pure latin squares. In this case the first mini-grid (1,1)mg is labeled canonically.

1 2 3
4 5 6
7 8 9

This reduces the total number of grids by 9!.

Band One
The number of possible combinations for the top row of (1,2)mg exists in two forms pure top rows and mixed top rows. Pure top rows are those in which the numbers {4,5,6} and {7,8,9} are used in nay order in the top rows of (1,2)mg and (1,3)mg.
For example the top row across the grid would be of the form
1 2 3 {4 5 6} {7 8 9}

1 2 3 {7 8 9} {4 5 6}
with the numbers in {} being in any order.
This gives:
1 2 3 {4 5 6} {7 8 9}
4 5 6 {7 8 9} {1 2 3}
7 8 9 {1 2 3} {4 5 6}

1 2 3 {7 8 9} {4 5 6}
4 5 6 {1 2 3} {7 8 9}
7 8 9 {4 5 6} {1 2 3}

As can be seen there are two variations (forwards and backwards). Each of these variations contain (3!)^6 combinations because the numbers in the brackets are interchangeable within the row. That is there are three combinations for the first number in the brackets, two choices for the second and then only one for the third in the bracket, giving (3!), as there are six of these possible combinations which are indepenent of one another than this gives a total of (3!)^6 combinations for the first three rows.
1 2 3 {n n-1 1} {n n-1 1}
4 5 6 {n n-1 1} {n n-1 1}
7 8 9 {n n-1 1} {n n-1 1}
Where n = 3
Mixed top rows are those in which {4,5,6,7,8,9} fall in any order across the top row.
There are 9 combinations of these and like the pure top rows they can be formed forwards and backwards.
These combinations are as follows:
{4,5,7} {6,8,9} {6,8,9} {4,5,7}
{4,5,8} {6,7,9} {6.7.9} {4,5,8}
{4,5,9} {6,7,8} {6,7,8} {4,5,9}
{4,5,7} {5,8,9} {5,8,9} {4,5,7}
{4,6,8} {5,7,9} {5,7,9} {4,6,8}
{4,6,9} {5,7,8} {5,7,8} {4,6,9}
{5,6,7} {4,8,9} {4,8,9} {5,6,7}
{5,6,8} {4,7,9} {4,7,9} {5,6,8}
{5,6,9} {4,7,8} {4,7,8} {5,6,9}

The numbers in the second row are equally as interchangeable as they do not form the strict top row pattern as the pure top row.
i.e. where as in the pure top row if the first column contained {1,2,3}{4,5,6}{7,8,9} then in the second row must contain {4,5,6}{7,8,9}{1,2,3} because none of the combinations can fall under their same combinations above because they would have multiple amounts of the same number in the same mini-grid.
As such the number 1,2,3 are interchangeable within the second row.
An example of which is
1 2 3 {4 5 7} {6 8 9}
4 5 6 {8 9 a} {7 b c}
7 8 9 {6 B c} {4 5 a}
Where a, b and c stand for 1, 2 and 3 in some order.
Thus giving 18 x 3 x (3!)^6.
At this stage the number of grid is equal to
(2 x (3!)^6) + (18 x 3 x (3!)^6) = 2,612,736
It should be noted here that for every one of the (3!)^6 combinations that occur using these properties numbers of total grids exist once the entire grid has been completed.

Stack One - Predictions
In the same way it is possible to arrange the grids (1,2)mg and (1,3)mg although once these are fixed, many of the reduction steps following cannot be performed in the same way. However if we take this number 2,612,736 for both the first column and first row, we are left with a grid in which the combinations that follow are determined in a predetermined way. That is once the combinations are discovered then the other components are fixed. For example
1 2 3 {4 5 6} {7 8 9}
4 5 6 {7 8 9} {1 2 3}
7 8 9 {1 2 3} {4 5 6}
{2 3 1}
{5 6 4}
{8 9 7}
{3 1 2}
{6 4 5}
{9 7 8}

One the middle block is calculated with the assumed 6! Combinations, as on each row or columns there is only a choice of six numbers as three have already been used in the starting grids, this leaves only three numbers in the final block of the stack or band which for the purpose of this estimation are assumed to be arranged in any combination (which is not true) and that the final mini-grid (3,3)mg has only one solution if the others are known.
As such it must follow that 2,612,7362 x 6! x 3! x 9! ≈ 1.07x1022
This gives us a not unreasonable upper bound for the total number of grids possible.

Reductions
To reduce the number along band one we can rearrange the columns in blocks (1,2)mg and (1,3)mg (and similarly in the entire grid) into numerical order on the 6 numbers giving 62 = 36 grids derived from it with the same number of ways of completing.
If we exchange grids (1,2)mg and (1,3)mg (and all of those in the middle and right stack) so that they can be lexicographically ordered then this halves the number of ways of completing. Thus giving a total reduction of a factor of 72.
2,612,736 / 72 = 36,288

Stack One
By taking the 6P6 permutations of the remaining six numbers along column a {2,3,5,6,8,9}, and by again reordering the rows of (2,1)mg and (3,1)mg we can reduce this by a factor of 72 (as explained above) leaving 10 possible combination types for this first column.

Processing
At this stage B. Felgenhauer and F. Jarvis used a C++ program to discover that given the properties above there are 3,546,146,300,288 combinations of grid.
The results of this program can be seen in appendix 2. It shows the different varieties of the reduced first band, the number of combinations this corresponds to (the sum of which is 36,288) and the number of possible SuDukos on the far right. The number of combinations are multiplied by the total SuDoku’s associated with it, and then totaled. Thus
3,546,146,300,288 x 72^2 x 9! = 6,670,903,752,021,072,936,960 number of SuDoku grids.