Mirrored from Sudopedia, the Free Sudoku Reference Guide

Mathematics of Sudoku

Contents

Basic Numerology

Let's consider some basic numerology about Sudoku. 

                         1.966270e+77  = # ways to randomly put digits 1 - 9 in 81 cells
                         1.091107e+50  = # ways to randomly put nine 1s, nine 2s, nine 3s,
                                         to nine 9s in 81 cells
5,524,751,496,156,892,842,531,225,600  = # Latin squares with digits 1 to 9
        6,671,248,172,291,458,990,080  = 5,472,730,538 * 3,359,232 * 362,880
        6,670,903,752,021,072,936,960  = Exact # of actual Sudoku solution grids
              377,597,570,964,258,816  = # Unique Latin squares with digits 1 to 9
               47,784,725,839,872,000  = (9!)^3 = ways to fill 3 blocks diagonally
                    1,218,998,108,160  = 3,359,232 * 362,880
                      948,109,639,680  = 9! × 2612736 # of possibilities for
                                         a floor in a Sudoku grid
                       17,179,869,184  = 4^17
                        8,589,934,592  = 2^33
                        5,472,730,538  = Exact # unique Sudoku solution grids
                        4,294,967,296  = 4^16 = 2^32
                           13,008,797  * current record for multiplicity of the MegaClue
                            3,359,232  = geometric permutations excluding relabeling
                              362,880  = # 9! number of ways to renumber a grid 
                                  729  = 9^3, which is also the dimensional space of Sudoku
                                  416  = # minimal floors
                                   39  * Record for the most clues in a minimal Puzzle
                                   17  * Record for the fewest clues in a minimal puzzle



5,524,751,496,156,892,842,531,225,600

There are 5,524,751,496,156,892,842,531,225,600 different Latin squares with the digits 1 to 9. See item number A002860 (Number of Latin squares of order n; or labeled quasigroups (Formerly M2051 N0812)) at The On-Line Encyclopedia of Integer Sequences.

6,671,248,172,291,458,990,080

If we multiple the (number of unique Sudoku solution grids) x (number of ways to renumber) x (the number of geometric permutations) we get:

5,472,730,538 * 3,359,232 * 362,880

which is equal to 6,671,248,172,291,458,990,080. This number is bigger than the actual number of different Sudoku solution grids because some of the geometric permutations result in identical arrangements.

6,670,903,752,021,072,936,960

This is the exact number of different Sudoku solution grids.


377,597,570,964,258,816

Suppose we canonicalize the Latin Squares to this pattern 

1 2 3 4 5 6 7 8 9
2 x x x x x x x x
3 x x x x x x x x
4 x x x x x x x x 
5 x x x x x x x x
6 x x x x x x x x
7 x x x x x x x x
8 x x x x x x x x
9 x x x x x x x x

Then there are:

5,524,751,496,156,892,842,531,225,600 /(9! x 8!) = 377,597,570,964,258,816

unique Latin squares with the digits 1 to 9


47,784,725,839,872,000

Consider one of the nine boxes in the Sudoku grid. 

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

There are 9! ways to renumber the cells in that block. Now consider the pattern: 

+-----------------------+ 
| X X X | . . . | . . . |
| X X X | . . . | . . . | 
| X X X | . . . | . . . | 
+-------+-------+-------+  
| . . . | Y Y Y | . . . |
| . . . | Y Y Y | . . . | 
| . . . | Y Y Y | . . . | 
+-------+-------+-------+
| . . . | . . . | Z Z Z |
| . . . | . . . | Z Z Z | 
| . . . | . . . | Z Z Z | 
+-------+-------+-------+

The three boxes X, Y, and Z don't interact directly with each other! So there are (9!)^3 = ways to fill 3 blocks diagonally.

The search for Sudoku puzzles with a high number of clues tends to produce puzzles with clues concentrated along the diagonals. Removing one clue from each block makes each block minimal.

1,218,998,108,160

If we multiple the (number of ways to renumber) x (the number of geometric permutations) we get the maximum number of permutations that a unique solution grid can contain.

3,359,232 * 362,880 = 1,218,998,108,160

Now not each unique solution grid will have this number of permutations since some of the permutations are identical. Consider a simplistic analogy. Let's look at a 4x4 Latin Square. 

1 2 3 4
2 3 4 1 
3 4 1 2 
4 1 2 3

Now if take the mirror image by flipping along the diagonal 

1 X X X
X 3 X X 
X X 1 X 
X X X 3

The same grid is obtained. 

1 2 3 4
2 3 4 1 
3 4 1 2 
4 1 2 3

Thus there are peculiar symmetries for certain solution grids that are random in nature. It is sort of like a cryptographic puzzle. Let's assume that the solution grids are known and have been numbered. Also all of the geometric permutations have been numbered. You are now given a number between 1 and 6,670,903,752,021,072,936,960. Unfortunately it is impossible what combination of unique solution grid and which permutation gives that number!

948,109,639,680

Consider a floor (or equivalently a tower) in a Sudoku grid. 

+-----------------------+ 
| . . . | . . . | . . . |
| . . . | . . . | . . . | 
| . . . | . . . | . . . | 
+-------+-------+-------+

Obviously by a simple renumbering any floor can be made to correspond with the floor below. Thus there are 9! arrangements for the first row. 

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

Now the second row doesn't have 9! possibilities. For instance r2c1 can't be a 1, 2, or a 3. If all the other permutations of the digits are tabulated there are 2,612,736 ways that rows 2 and 3 can be completed and still be consistent with the rules of Sudoku. Thus there are

9! × 2612736 = 948,109,639,680 of possibilities for a floor in a Sudoku grid

Of the 2612736 possibilities for a floor where the first row is 123456789, there are 416 unique ways to complete the floor.

17,179,869,184

17,179,869,184 just seems like an interesting number since it is the power of four just above the actual number of unique Sudoku solution grids.

4^17 = 17,179,869,184

8,589,934,592

8,589,934,592 just seems like an interesting number since it is the power of two just above the actual number of unique Sudoku solution grids.

2^33 = 8,589,934,592

5,472,730,538

There are exactly 5,472,730,538 unique Sudoku solution grids.

(discuss compressing list which is quite interesting ...)

4,294,967,296

4,294,967,296 just seems like an interesting number since it is the power of two just below the actual number of unique Sudoku solution grids.

2^32 = 4^16 = 4,294,967,296

3,359,232

3,359,232 is the number geometric permutations excluding relabeling. It is a rather odd number at first glance.

2 x 6^8 = 3,359,232

but it isn't so formidable to calculate. Let's consider towers. There are three towers which have six possible arrangements: 

123   132   213   231   312   321

So if we summarize over all the allow swapping we have:

6 = ways three towers can be arranged.

6 = ways that three floors can be arranged

6 = ways that three rows in floor 1 can be arranged

6 = ways that three rows in floor 2 can be arranged

6 = ways that three rows in floor 3 can be arranged

6 = ways that three columns in tower 1 can be arranged

6 = ways that three columns in tower 2 can be arranged

6 = ways that three columns in tower 3 can be arranged

So this gives us the 6^8 part of the magic number. The 2 reflects the fact that if you take a mirror image along the diagonal, then permutations of floors, towers, rows or columns can't create the corresponding permutation.

362,880

Let's consider a "random" grid for which the first line is 

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

Let's renumber the grid with the following scheme: 

6 = 1
3 = 2
4 = 3
8 = 4
1 = 5
9 = 6
2 = 7
5 = 8
7 = 9

to get: 

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

Obviously by a simple renumbering the first row of any grid can be made to correspond with the first row shown above. Thus there are 9! arrangements for the first row which can be renumbered to the target row 123456789.

9! = 362,880 = number of ways to renumber a grid

729

9^3

Also it is possible to think of all of the possible Sudoku grids as being on the surface of a 729 dimensional space. This higher-dimensional analogue of 2-D polygons and 3-D polyhedra is called a polytope. The polytope is a nice model since it allows movement from one solution grid to the next.

Clues

Arithmetic Analysis

Since the digits 1 to 9 are used for a house, it is possible to create equations which define relationships between the cells in a family. For instance the integers from 1 to 9 add to 45, and the product of the integers is 362,880 (or 9!). However there isn't any real significance in using numbers to play Sudoku.

The digits used on the normal 9x9 could just as easily be replaced by nine different symbols (e.g., ♠ ♣ ♥ ♦ ♫ ☺ □ ▼ ☼ ) . Consider the following "mathematical equation." What does a spade plus a heart divided by a note mean? 


(♠ + ♥ ) / ♫ = ?

The sum and the product of the digits really provides a glimpse into a deeper relationship based in set theory.

(1) There are nine different symbols.

(2) Each symbol must be used once and only one in a set known as a house.

The gist of this is a fairly simple concept. Suppose there are a four cells open in the house. If there are 3 choices in the first open cell, and 2 choices in the second, and 4 choices in the third and 3 choices in the fourth, then there are not 3*2*4*3 choices overall. Rather the choices can be considered to be made together as a set of four choices. Hence the set properties constrain the choices. Linear equations is just one way that the constraints can be expressed.


Clues For Valid Puzzles

Number of Clues for a Valid Puzzle

Average Number of Clues for a Valid Puzzle

Clues for Minimal Puzzles

Minimum Number of Clues for a Minimal Puzzle

Maximum Number of Clues for a Minimal Puzzle

Average Number of Clues for a Minimal Puzzle

Restrictions on Clues for a Minimal Puzzle

Must use at least 8 of 9 digits

Multiplicity Of The Megaclue

Obviously if you remove a clue form a minimal puzzle, then there will be multiple solutions.

2 is obviously the smallest number of multiple solutions that removing a clue can create.

But what clue in what puzzle creates the most multiple solutions? What is the Multiplicity of the Megaclue?

Removing the 6 at r2c3 from this puzzle... 


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

and you get 13,008,797 grid solutions !

http://forum.enjoysudoku.com/post204177.html#p204177

Group theory for Sudoku

Application to Solution Grids

Canonical Solution Grids

Renumbering Solution Grids

Geometric Permutations of Solution Grids

Classes of Symmetry

Application to Puzzle Patterns

The idea behind puzzle patterns is that the pattern of the clues becomes a template which simply indicates if a clue is present or not at a particular cell position. A more detailed explanation will be found on the wiki page on Sudoku Puzzle Symmetries. The following sections on Symmetry Operations and Sudoku Puzzle Symmetry Groups will summarize the results.

Symmetry Operations

The following operations on a puzzle pattern are possible.

Sudoku Puzzle Symmetry Groups

Now the operations above are not independent. For example you can't have four-fold rotational symmetry without having two-fold rotational symmetry.

Impossible Patterns

Complexity of Sudoku

Complexity of creating a puzzle

Complexity of Solving a Puzzle

Rating the Difficulty of Puzzles

Conjectures

Unknown

Conjectures are easy to make, and very difficult to prove. Regardless of how many times the conjecture works, one counter-example would prove the conjecture false.

17 Clue Conjecture

The 17 Clue Conjecture states that 17 clues is the fewest necessary for any minimal puzzle.

39 Clue Conjecture

The 17 Clue Conjecture states that 39 clues is the maximum that any minimal puzzle can have.

Proved false

Singles Backdoor Conjecture

The Singles Backdoor Conjecture claims that the maximum minimal singles backdoor size is 2. Equivalently each 9x9 Sudoku has a backdoor of size at most 2 that when solved renders the puzzle solvable by singles only.

http://forum.enjoysudoku.com/post40177.html#p40177

Adding clues can't make a puzzle more difficult

The following puzzle proves this conjecture wrong. 

8 . . | 2 . 5 | . . 1
. . . | 1 . 3 | . . .
. . 3 | . 7 . | 8 . .
------+-------+------
6 3 . | . . . | . 7 5
. . 8 | . . . | 2 . .
9 1 . | . . . | . 4 8
------+-------+------
. . 5 | . 9 . | 1 . .
. . . | 7 . 6 | . . .
3 . . | 5 . 2 | . . 9   S.E. 4.5

But adding a clue, the 9 at cell r3c6, raises the score of the puzzle! 

8 . . | 2 . 5 | . . 1
. . . | 1 . 3 | . . .
. . 3 | . 7 9 | 8 . .
------+-------+------
6 3 . | . . . | . 7 5
. . 8 | . . . | 2 . .
9 1 . | . . . | . 4 8
------+-------+------
. . 5 | . 9 . | 1 . .
. . . | 7 . 6 | . . .
3 . . | 5 . 2 | . . 9   S.E. 7.2

Of course this assumes that SE rates the difficulty of puzzles properly.

http://forum.enjoysudoku.com/post26244.html#p26244

External links

This page was last modified 22:48, 26 October 2010.