How may possible Sudoku Solution Grids are there? The correct answer is: $6,670,903,752,021,072,936,960$ or $6,671E21$ as was proved $12$ years ago! Or was it?
Their proof never really enumerated the solutions and involved a lot of mainframe time to compute, which involved a lot of reducing test cases to make the computations complete in human time.
When they said and I read that no simple combinatorial answer was possible, I immediately though, "Well I already know one."
So I ran the numbers on a calculator but did NOT get their solution and I can't see a flaw in mine.
I can not follow there solution to the end since I have to rely on their computer results. I sent this to the author but did not hear back, which is not surprising since it is not there place to prove me wrong. I have waited and looked over my method long enough that I stand by my solution.
Since this has to be expressed in the form of a question, "What is wrong with my solution?"
So, here is, what we have all been waiting for:
My Simple Combinatorial Way to Enumerate Sudoku Solution Grids
Note: The problem we are trying to solve here is for N0 which is the maximum number of correct Sudoku answer grids. So, no discussion of swapping to get equivalent solutions.
There are three Bands, rows $1$-$3$, $4$-$6$, and $7$-$9$, and three Stacks columns $1$-$3$, $4$-$6$, and $7$-$9$ in a Sudoku Grid. We will start with a discussion of the first Band which is the top three rows.
The three bands and stacks divide the Sudoku Grid in to $9$ Blocks, labeled $B_1$, $B_2$, and $B_3$ in Band$1$, $B_4$, $B_5$, and $B_6$ in Band$2$, and $B_7$, $B_8$, and $B_9$ in Band$3$, which also means $B_1$, $B_4$, and $B_7$ in Stack$1$, $B_2$, $B_5$, and $B_8$ in Stack$2$, and $B_3$, $B_6$, and $B_9$ in Stack$3$.
Substituting Numbers for Symbol Positions
We will substitute the $9$ numbers used in the $81$ squares to leave $B_1$ with the following Grid:
|1 2 3| |4 5 6| Note: 9! cases |7 8 9|
With this we can now think of the numbers not as number but as symbol positions, where $9!$ different solutions will use the same symbol positions for all the $81$ squares.
Describing Row Constraints for a Band
Say we want to fill in Band1 and we start in what I call an All-Normal Pattern for $B_1$ Row$1$, as follows:
Row 1: |1 2 3| | | Note: The symbol positions in B2 and Row 2: |4 5 6|1 2 3| | B3 only describe the row they are in, Row 3: |7 8 9| |1 2 3| not the column positions.
Given this as a starting point, how do we fill in the symbol positions from the $B_1$ Row2, in $B_2$? If we tried to put them in Row1 we have a problem when we get to B3 because we would need to use positions already occupied. So, we have to follow the same All-Normal pattern as $B_1$ Row1, resulting in the following:
Row 1: |1 2 3| |4 5 6| Note: The symbol positions in B2 and Row 2: |4 5 6|1 2 3| | B3 only describe the row they are in, Row 3: |7 8 9|4 5 6|1 2 3| not the column positions.
Then $B_1$ Row$3$ follows the All-Normal pattern to fill in the blanks.
A Normal Symbol is defined as a symbol that goes down one to the second block and down one to the third block, where if you go below the bottom you wrap to the top of the band.
Abnormal Symbol is defined as a symbol that goes down two to the second block and down two to the third block, with wrapping.
An All-Normal Pattern is where all nine symbols are normal.
Now lets look at a case with one abnormal symbol from $B_1$ Row$1$, we will pick $3$:
Row 1: |1 2 3| | | Note: The symbol positions in B2 and Row 2: |4 5 6|1 2 | 3| B3 only describe the row they are in, Row 3: |7 8 9| 3|1 2 | not the column positions.
Here we have the symbol $3$ going down $2$, and down $2$ with a wrap, instead of down $1$ and down $1$.
Now if we try to fill in $B_1$ Row$2$ and Row$3$ in $B_2$ and $B_3$ we find that we have a similar problem, unless we do the same thing as Row$1$ and pick one of the three symbols to be abnormal. The same thing can be said about having two abnormals from Row$1$, we need to repeat this for the other two Rows. And finally we have the three abnormals case. For brevity I will leave it to the reader to validate this or they can just look at any Sudoku solution grid.
Abnormal Pattern is defined as having one abnormal symbol per row in $B_1$.
Normal Pattern is defined as having one normal symbol per row in $B_1$.
All-Abnormal Pattern is defined as all $27$ symbols being abnormal.
The normal and abnormal patterns need further clarification. For normal pattern we need to know, which of the three positions in each row in B1 contains the normal symbol. For abnormal pattern we need the same for the abnormal symbol. For each row there are $3$ positions for a total of $3\times3\times3 = 27$.
So the total number of permutations of symbols into rows in $B_2$ and $B_3$ for Band$1$ is $1$ for the All-Normal, $3\times3\times3$ for the Abnormal, $3\times3\times3$ for the Normal, and $1$ for the All-Abnormal patterns. Let us call this $R$:
R = 1 + 3*3*3 + 3*3*3 + 1 = 56 permutations of 9 symbols in 3 rows.
It should be noted that $R$ describes all three blocks even if you were to swap them, it is a natural constraint on any block/stack and we can use it later to describe all $3$ blocks and $3$ stacks.
The rest is trivial, but I will highlight the important parts.
Describing Column Constraints for $B_2$ and $B_3$
We still need to describe the column positions for the symbols in $B_2$ and $B_3$, which is just the permutations of the three number in each sub-row, which is $6$. Let us call this $P$:
P = 6*6*6 * 6*6*6 = 6*6 * 6*6 * 6*6 = 46656 permutations of 3 symbols in 6 sub-rows.
Implementation Note: Because in the Normal and Abnormal cases the one value will end up in a different row then the other two, When doing the permutations only permute two symbols, $A$ and $B$, through three positions:
|A B x|, |A x B|, |x A B|, |B A x|, |B x A|, |x B A|
Where $A$ and $B$ are:
|A B x| For each row in B1 in the All-Normal and All-Abnormal patterns. |x A B| For each row in B1 where, |A x B| in the Abnormal pattern, x is the position of abnormal symbol and, |A B x| in the Normal pattern, x is the position normal symbol.
The remaining character x will find its position as the open position in its assigned row.
So for Band$1$ the total number of solutions using symbol positions is:
R * P = 56 * 46656 = 2612736
Note: I can use a number between $1$ through $2612736$ to calculate a specific permutation of these solutions or I can use a solution and use the above discussion to assign a specific number to this permutation.
The Constraining the Rest of the Bands and Stacks
If I want to describe the starting positions for $B_4$ and $B_7$ I can use $R$ and $P$ for Stack$1$ like I did for Band1 and know all the permutations of $B_4$ and $B_7$. Unimportant Note: Later I could do some renumbering for $B_1$ when describing Stack$1$ to gain symmetry for the final row and column descriptions.
$R$ can be used on Band$2$ and Band$3$ to describe the row positions for $B_5$, $B_6$, $B_8$, and $B_9$.
$R$ can be used on Stack$2$ and Stack$3$ to describe the column positions for $B_5$, $B_6$, $B_8$, and $B_9$.
If I know the row and column positions for each symbol for $B_5$, $B_6$, $B_8$, and $B_9$ then the completion of each permutation just involves matching the row and column for each symbol for each block.
I can describe Band$1$ and the row positions in Band$2$ and Band$3$ as:
Row Contribution = R * P * R * R = 8,193,540,096
I can describe Stack$1$ and the column positions in Stack$2$ and Stack$3$ as:
Column Contribution = R * P * R * R = 8,193,540,096
The total is just multiplying these two numbers and $9!$ for substituting numbers for symbol positions
Total = 9! * 8,193,540,096 * 8,193,540,096 = 2.436162195571x10^25
Since it is just multiplying digits I could list all the digits but my math package does not have that may significant digits.
Unimportant Note: It might be good to swap the $P$s between the two contributions since the $P$ in row contribution fixes the column positions and vice versa, or not.
So, now I have a total of numbers solutions and a design for a function that, given a number in this range, I can derive a specific solution or given a solution, I can derive its ordinal number and I know how to count through all solutions.
Humorous note: $8,193,540,096 \times 8,193,540,096 = 6.7134E19$
So again, where is my mistake?