4
$\begingroup$

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.

Conclusion

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?

$\endgroup$
  • $\begingroup$ How does your method ensure that, e.g., there isn't a 1 in row 2 column 4 and also in row 6 column 4? $\endgroup$ – Steven Stadnicki Mar 9 '18 at 23:41
  • $\begingroup$ (More to the point, when you multiply the 'row contribution' and the 'column contribution' together, you're actually talking about the number of configurations of two 9x9 grids: one that satisfies the row constraints and one that satisfies the column constraints.) $\endgroup$ – Steven Stadnicki Mar 9 '18 at 23:43
  • $\begingroup$ R for Stack2 confines the column positions for B5 and B7 which assures that 1 can't be in the same column in row 2 and row 6. $\endgroup$ – Sojourner9 Mar 10 '18 at 16:28
  • $\begingroup$ "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." I don't understand this. Do you want to calculate the number of different valid sudoku grids? If so, about what maximum are you talking and what does the sentence about "swapping" mean? $\endgroup$ – miracle173 Mar 12 '18 at 12:28
  • $\begingroup$ Miracle173, When I read these papers it was confusing what they were trying to calculate and I hoped that these two sentences would make it clear. I might ask what you mean by different? Think how that might confuse some on what you are asking? If I hold a Sudoku grid up to a mirror is it different? For N0 the answer is yes, the mirror image is just another permutation in the enumeration of results. $\endgroup$ – Sojourner9 Mar 12 '18 at 18:25
5
$\begingroup$

I have a slighly different naming. Block$_{11}$ is the left upper $3\times 3$ block.

First I want do describe your method to count the sudokus. Then I want to show the error and the I give an example that shows that your method does not work. You try to generate each sudoku in the following way

  1. define Block$_{11}$ of the sudoku there are 9! possibilities

  2. define Block$_{12}$ and Block$_{13}$

    1. select three sets: the first set contains the numbers of the first row of Block$_{12}$, the second set contains the numbers of the second row of Block$_{12}$, the third set contains the numbers of the third row of Block$_{12}$. These sets should satisfy the sudoku constraints with respect to Block$_{11}$ and Block$_{12}$ and should allow to create three sets with similar meaning for Block$_{13}$. You already showed that there are at most 56 (=R) possible sets triples. All other triples of sets will lead to a contradiction to the sudoku constraints with regard to the first three rows. From the sets you selected you can deduce three sets that are the numbers of the first, second and third row of Block$_{13}$
    2. in 2.1 you have created 6 sets of length 3. For each set select a permutation of its elements. this is then the actual row of the sudoku. you already showed there $(3!)^6$ (=P)possibilities to select 6 such permutations.
  3. Define Block$_{21}$ ad Block$_{31}$ in a similar way like Block$_{12}$ and Block$_{13}$ in 2. But now the sets represent the numbers of the columns of the blocks. Again there are $R \cdot P$ posibilities.

Now you have fixed the numbers of the cells of Block$_{11}$, Block$_{12}$, Block$_{13}$, Block$_{21}$ and Block$_{31}$.

    1. Define column sets for Block$_{22}$ and the deduced sets for Block$_{32}$. There are R possibilities
    2. Define column sets for Block$_{23}$ and the deduced sets for Block$_{33}$. There are R possibilities
    3. Define row sets for Block$_{22}$ and the deduced sets for Block$_{23}$. There are R possibilities
    4. Define row sets for Block$_{32}$ and the deduced sets for Block$_{33}$. There are R possibilities
  1. For each cell of the four blocks mentioned in 4. construct the uniquely defined number that satisfies the given column and row set

Using Steps 1 to 3 you have $9!\times (R\times P)^2$ to assign numbers to the cells of Block$_{11}$, Block$_{12}$, Block$_{13}$, Block$_{21}$, Block$_{31}$ consistently. Consistently means that each of these Blocks, each of the top 3 rows and each of the left 3 lines contains each of the numbers 1 to 9 exactly once.

Then you say you have $R^4$ ways to select the sets that contain the numbers of the rows and columns of Block$_{22},$ Block$_{23},$ Block$_{32}$ and Block$_{33}.$ Such sets must be chosen in away similar to 2. and 3. Such a selection of sets consists of the set that contains the numbers of the first row of Block$_{22},$ the set that contains the the numbers of second row of Block$_{22}$ and the set that contains the numbers of the third row of Block$_{22}.$ Then we have three sets that contains the numbers of the first, second ad third column of Block$_{22}.$ So all in all we have to choose 6 sets for Block$_{22}$. For Block$_{23},$ Block$_{32}$ and Block$_{33}$ we have to choose six sets respectively, too. So each of these $R^4$ selections consists of 24 sets with 3 elements that resticts the values of Block$_{22},$ Block$_{23},$ Block$_{32}$ and Block$_{33}.$

But in 5 you state that for each of such selection of 24 sets there is ecactly one number for each cell that satisfies the the constraints imposed by the sets.

But you neither proved that for each such selection of 24 sets there is at least one assignement to the cells that satisfies the constraints imposed by such a 24 sets nor that there is at most one assignement that satisfies these constraints.

An example: Here we have a sudoku

6 7 8 | 4 5 3 | 2 9 1
5 9 4 | 8 2 1 | 7 3 6
1 3 2 | 6 9 7 | 5 4 8
------+-------+------
2 6 1 | 3 7 8 | 4 5 9
9 8 7 | 1 4 5 | 3 6 2
3 4 5 | 9 6 2 | 1 8 7
------+-------+------
7 5 9 | 2 3 6 | 8 1 4
8 2 6 | 5 1 4 | 9 7 3
4 1 3 | 7 8 9 | 6 2 5 

Assume you have actually executed step 1 to 4.3. (and in the following diagram you have actually assigend numbers to the cells of Block$_{22}$ and Block$_{23}$) To the cells in Block$_{32}$ and Block$_{33}$ we did not have assigned values.

6 7 8 | 4 5 3 | 2 9 1
5 9 4 | 8 2 1 | 7 3 6
1 3 2 | 6 9 7 | 5 4 8
------+-------+------
2 6 1 | 3 7 8 | 4 5 9
9 8 7 | 1 4 5 | 3 6 2
3 4 5 | 9 6 2 | 1 8 7
------+-------+------
7 5 9 |       |      
8 2 6 |       |      
4 1 3 |       |      

Now we assign the following sets to the rows and columns of Block$_{32}$ and Block$_{33}$.

      row sets (interchanged the row sets of 
      Block32 and Block33 of the original sudoku):
------+-------+------
      |       |      
      |       |      
      |       |      
------+-------+------
      |       |      
      |       |      
      |       |      
------+-------+------
      { 1 4 8 { 2 3 6 
      { 3 7 9 { 1 4 5
      { 2 5 6 { 7 8 9

      column sets (the same as for the original sudoku):
------+-------+------
      |       |      
      |       |      
      |       |      
------+~~~~~~~+~~~~~~
      | 1 4 2 | 1 5 2
      | 3 6 5 | 3 6 7
      | 9 7 8 | 4 8 9
------+~~~~~~~+~~~~~~
      | 2 1 4 | 6 1 3
      | 5 3 6 | 8 2 4
      | 7 8 9 | 9 7 5

The { and the ~ should remind you that the rows and columns of the Block$_{23}$ and Block$_{33}$ aren't actually the rows and the columns of these two blocks but the sets assigned to these rows and columns.

These sets are constructed according to your requirements but there is now assignment to the cells of Block$_{33}$ that can satisfy the requirements. But Block$_33$ cannot satisfy these sets.

      |       |       
      |       |       
      |       |       
------+-------+-------
      |       |       
      |       |       
      |       |       
------+-------+-------
      |       | 6 2 3      
      |       | ?     
      |       |       

There is no valid number for cell$_{87}$. The number should be in {1, 4, 5} (row set) and {6,8,9} (column set). But he intersection of these set is the empty set.

But you count that there are actually R sudokus that satisfy these constraints.

Note: Maybe you want to read my answer at stackoverflow where I cite Kevin Kinfoil's post that tries to estimate the number of possible Sudokus by using similar heuristic arguments. He arrives at a number that differs only 0.2% from the true value. This heuristic argumentation was posted before the true value was known.

Note: The number of possible sudokus where calculated first by Jarvis & Felgenhauer.

$\endgroup$
  • $\begingroup$ In your example for Stack1 I get an Rvalue of Abnormal233 because only 8, 9 and 7 follow the abnormal path. Stack2 gets an Rvalue of Normal311 because only 5, 9, and 1 follow the normal path. Band2 gets an Rvalue of Normal311 because only 1, 9, 3 and follow the normal path. Band3 gets an Rvalue of Normal213 because only 5, 8, and 3 follow the Normal path. This can be done for any valid answer and there are no valid answers on which it can not be done. $\endgroup$ – Sojourner9 Mar 14 '18 at 17:48
  • $\begingroup$ I found some error in my post. In the descrition of the algorithm and in the example. I will correct this. $\endgroup$ – miracle173 Mar 15 '18 at 4:40
  • $\begingroup$ So what I learned was that my Rnumbers can describe any Sudoku once I see it but that not all combinations are possible because of packing constraints. So I can't just enumerate all the possibilities become some won't work. Thanks $\endgroup$ – Sojourner9 Mar 16 '18 at 14:19
  • $\begingroup$ replaced the example by a correct one. cn you check it. And could you remove old comments that aren't needed anymore. $\endgroup$ – miracle173 Mar 16 '18 at 18:11
  • $\begingroup$ Synopsis if the comments I deleted. Thanks for your effort on this as I really want to know If I am wrong. And again, what I learned is that from a valid answer I can go back to Rvalues and from Rvalues to the same answer; But, I can't start off just with Rvalues and expect the answer to be valid. They can describe but not predict. $\endgroup$ – Sojourner9 Mar 17 '18 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.