he addition table in {\displaystyle \mathbb {Z} _{3}\oplus \mathbb {Z} _{3}} {\mathbb {Z}}_{{3}}\oplus {\mathbb {Z}}_{{3}}
(0,0) (0,1) (0,2)
(0,1) (0,2) (0,0)
(0,2) (0,0) (0,1)
(1,0) (1,1) (1,2)
(1,1) (1,2) (1,0)
(1,2) (1,0) (1,1)
(2,0) (2,1) (2,2)
(2,1) (2,2) (2,0)
(2,2) (2,0) (2,1)
(1,0) (1,1) (1,2)
(1,1) (1,2) (1,0)
(1,2) (1,0) (1,1)
(2,0) (2,1) (2,2)
(2,1) (2,2) (2,0)
(2,2) (2,0) (2,1)
(0,0) (0,1) (0,2)
(0,1) (0,2) (0,0)
(0,2) (0,0) (0,1)
(2,0) (2,1) (2,2)
(2,1) (2,2) (2,0)
(2,2) (2,0) (2,1)
(0,0) (0,1) (0,2)
(0,1) (0,2) (0,0)
(0,2) (0,0) (0,1)
(1,0) (1,1) (1,2)
(1,1) (1,2) (1,0)
(1,2) (1,0) (1,1)
Grid 2 - Generating a Sudoku
(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)
(0,0) (0,1) (0,2)
(2,0) (2,1) (2,2)
(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(0,1) (0,2) (0,0)
(1,1) (1,2) (1,0)
(2,1) (2,2) (2,0)
(1,1) (1,2) (1,0)
(2,1) (2,2) (2,0)
(0,1) (0,2) (0,0)
(2,1) (2,2) (2,0)
(0,1) (0,2) (0,0)
(1,1) (1,2) (1,0)
(0,2) (0,0) (0,1)
(1,2) (1,0) (1,1)
(2,2) (2,0) (2,1)
(1,2) (1,0) (1,1)
(2,2) (2,0) (2,1)
(0,2) (0,0) (0,1)
(2,2) (2,0) (2,1)
(0,2) (0,0) (0,1)
(1,2) (1,0) (1,1)
For this method to work, one generally does not need a product of two equally-sized groups. A so-called short exact sequence of finite groups of appropriate size already does the job. Try for example the group {\displaystyle \mathbb {Z} _{4}} {\mathbb {Z}}_{{4}} with quotient- and subgroup {\displaystyle \mathbb {Z} _{2}} \mathbb {Z} _{2}. It seems clear (already from enumeration arguments), that not all Sudokus can be generated this way.
Enumerating Sudoku solutions
The answer to the question 'How many Sudoku grids are there?' depends on the definition of when similar solutions are considered different.
Enumerating all possible Sudoku solutions
For the enumeration of all possible solutions, two solutions are considered distinct if any of their corresponding (81) cell values differ. Symmetry relations between similar solutions are ignored., e.g. the rotations of a solution are considered distinct. Symmetries play a significant role in the enumeration strategy, but not in the count of all possible solutions.
The first known solution to complete enumeration was posted by QSCGZ [Guenter Stertenbrink] to the rec.puzzles newsgroup in 2003,[6][10][11] obtaining 6,670,903,752,021,072,936,960 (6.67×1021) distinct solutions.
In a 2005 study, Felgenhauer and Jarvis[12] analyzed the permutations of the top band used in valid solutions. Once the Band1 symmetries and equivalence classes for the partial grid solutions were identified, the completions of the lower two bands were constructed and counted for each equivalence class. Summing completions over the equivalence classes, weighted by class size, gives the total number of solutions as 6,670,903,752,021,072,936,960, confirming the value obtained by QSCGZ. The value was subsequently confirmed numerous times independently. A second enumeration technique based on band generation was later developed that is significantly less computationally intensive.
Enumerating essentially different Sudoku solutions
Two valid grids are essentially the same if one can be derived from the other. The following operations are Sudoku preserving symmetries and always translate a valid grid into another valid grid:
Relabeling symbols (9!)
Band permutations (3!)
Row permutations within a band (3!3)
Stack permutations (3!)
Column permutations within a stack (3!3)
Reflection, transposition and rotation (2). (Given any transposition or quarter-turn rotation in conjunction with the above permutations, any combination of reflections, transpositions and rotations can be produced, so these operations only contribute a factor of 2.)
These operations define a symmetry relation between equivalent grids. Excluding relabeling, and with respect to the 81 grid cell values, the operations form a subgroup of the symmetric group S81, of order 3!8×2 = 3,359,232. Applying the above operations on majority of the grids results in 3!8×2×9! essentially equivalent grids. Exceptions are Automorphic Sudokus which due to additional non-trivial symmetry generate fewer grids.
The number of distinct solutions can also be identified with Burnside's Lemma. For a solution, the set of equivalent solutions which can be reached using these operations (excluding relabeling), form an orbit of the symmetric group. The number of essentially different solutions is then the number of orbits, which can be computed using Burnside's lemma. The Burnside fixed points are solutions that differ only by relabeling. Using this technique, Jarvis/Russell[7] computed the number of essentially different (symmetrically distinct) solutions as 5,472,730,538.
Enumeration results
Enumeration results for many Sudoku variants have been calculated: these are summarised below.
Sudoku with rectangular regions
In the table, "Dimensions" are those of the regions (e.g. 3x3 in normal Sudoku). The "Rel Err" column indicates how a simple approximation, using the generalised method of Kevin Kilfoil,[13] compares to the true grid count: it is an underestimate in all cases evaluated so far.
{\displaystyle {\mbox{Number of Grids}}\simeq {\frac {b_{R,C}^{C}\times b_{C,R}^{R}}{(RC)!^{RC}}}} {\mbox{Number of Grids}}\simeq {\frac {b_{{R,C}}^{C}\times b_{{C,R}}^{R}}{(RC)!^{{RC}}}}
where bR,C is the number of ways of completing a Sudoku band[2] of R horizontally adjacent R×C boxes. Petersen's algorithm,[26] as implemented by Silver,[27] is currently the fastest known technique for exact evaluation of these bR,C.
The band counts for problems whose full Sudoku grid-count is unknown are listed below. As in the previous section, "Dimensions" are those of the regions.
The expression for the 4×C case is: {\displaystyle (4C)!(C!)^{12}\sum _{a,b,c}{\left({\frac {C!^{2}}{a!b!c!}}\cdot \sum _{k_{12},k_{13},k_{14}, \atop k_{23},k_{24},k_{34}}{{a \choose k_{12}}{b \choose k_{13}}{c \choose k_{14}}{c \choose k_{23}}{b \choose k_{24}}{a \choose k_{34}}}\right)^{2}}} (4C)!(C!)^{{12}}\sum _{{a,b,c}}{\left({\frac {C!^{2}}{a!b!c!}}\cdot \sum _{{k_{{12}},k_{{13}},k_{{14}}, \atop k_{{23}},k_{{24}},k_{{34}}}}{{a \choose k_{{12}}}{b \choose k_{{13}}}{c \choose k_{{14}}}{c \choose k_{{23}}}{b \choose k_{{24}}}{a \choose k_{{34}}}}\right)^{2}}
where:
the outer summand is taken over all a,b,c such that 0<=a,b,c and a+b+c=2C
the inner summand is taken over all k12,k13,k14,k23,k24,k34 = 0 such that
k12,k34 = a and
k13,k24 = b and
k14,k23 = c and
k12+k13+k14 = a-k12+k23+k24 = b-k13+c-k23+k34 = c-k14+b-k24+a-k34 = C
Sudoku with additional constraints
The following are all restrictions of 3x3 Sudokus. The type names have not been standardised: click on the attribution links to see the definitions.
Type Nr Grids Attribution Verified?
Quasi-Magic Sudoku 248832 Jones, Perkins and Roach[33] Yes
3doku 104015259648 Stertenbrink[34] Yes
Disjoint Groups 201105135151764480 Russell[35] Yes
Hypercube 37739520 Stertenbrink[36] Yes
Magic Sudoku 5971968 Stertenbrink[37] Yes
Sudoku X 55613393399531520 Russell[38] Yes
NRC Sudoku 6337174388428800 Brouwer[39] Yes
A Sudoku will remain valid under the actions of the Sudoku preserving symmetries (see also Jarvis[7]). Some Sudokus are special in that some operations merely have the effect of relabelling the digits; several of these are listed below.
Transformation Nr Grids Verified?
Transposition 10980179804160 Indirectly
Quarter Turn 4737761280 Indirectly
Half Turn 56425064693760 Indirectly
Band cycling 5384326348800 Indirectly
Within-band row cycling 39007939461120 Indirectly
Further calculations of this ilk combine to show that the number of essentially different Sudoku grids is 5,472,730,538, for example as demonstrated by Jarvis / Russell[7] and verified by Pettersen.[40] Similar methods have been applied to the 2x3 case, where Jarvis / Russell[41] showed that there are 49 essentially different grids (see also the article by Bailey, Cameron and Connelly[42]), to the 2x4 case, where Russell[43] showed that there are 1,673,187 essentially different grids (verified by Pettersen[44]), and to the 2x5 case where Pettersen[45] showed that there are 4,743,933,602,050,718 essentially different grids (not verified).
Minimum number of givens
Ordinary Sudokus (proper puzzles) have a unique solution. A minimal Sudoku is a Sudoku from which no clue can be removed leaving it a proper Sudoku. Different minimal Sudokus can have a different number of clues. This section discusses the minimum number of givens for proper puzzles.
Ordinary Sudoku
A Sudoku with 17 clues.
A Sudoku with 17 clues and diagonal symmetry.[46]
A Sudoku with 18 clues and orthogonal symmetry.[47]
An automorphic Sudoku with 24 clues and complete geometric symmetry.[48]
A Sudoku with 19 clues and two-way orthogonal symmetry.[49]
Many Sudokus have been found with 17 clues, although finding them is not a trivial task.[50][51] A paper by Gary McGuire, Bastian Tugemann, and Gilles Civario, released on 1 January 2012, explains how it was proved through an exhaustive computer search that the minimum number of clues in any proper Sudoku is 17,[52][53][54] and this was independently confirmed in September 2013.[55] A few 17-clue puzzles with diagonal symmetry were provided by Ed Russell, after a search through equivalence transformations of Gordon Royle's database of 17-clue puzzles.[56][46] Sudoku puzzles with 18 clues have been found with 180° rotational symmetry, and others with orthogonal symmetry, although it is not known if this number of clues is minimal in either case.[47] Sudoku puzzles with 19 clues have been found with two-way orthogonal symmetry, and again it is unknown if this number of clues is minimal for this case.[49]
A Sudoku with 24 clues, dihedral symmetry (symmetry on both orthogonal axis, 90° rotational symmetry, 180° rotational