Mathematics of Sudoku

Sudoku puzzles can be studied mathematically to answer questions such as "How many filled Sudoku grids are there?", "What is the minimal number of clues in a valid puzzle?" and "In what ways can Sudoku grids be symmetric?" through the use of combinatorics and group theory.
The main results are that for the classical Sudoku the number of filled grids is 6,670,903,752,021,072,936,960 (), which reduces to 5,472,730,538 essentially different groups under the validity preserving transformations. There are 26 types of symmetry, but they can only be found in about 0.005% of all filled grids. A puzzle with a unique solution must have at least 17 clues, and there is a solvable puzzle with at most 21 clues for every solved grid. The largest minimal puzzle found so far has 40 clues.
Similar results are known for variants and smaller grids. No exact results are known for Sudokus larger than the classical 9×9 grid, although there are estimates which are believed to be fairly accurate.
Overview.
The analysis of Sudoku falls into two main areas:
Initial analysis was largely focused on enumerating solutions, with results first appearing in 2004.
There are many Sudoku variants, partially characterized by size ("N"), and the shape of their "regions". Unless noted, discussion in this article assumes classic Sudoku, i.e. "N"=9 (a 9×9 grid and 3×3 regions). A rectangular Sudoku uses rectangular regions of row-column dimension "R"×"C". Other variants include those with irregularly-shaped regions or with additional constraints (hypercube) or different constraint types (Samunamupure).
Regions are also called "blocks" or "boxes". A "band" is a part of the grid that encapsulates 3 rows and 3 boxes, and a "stack" is a part of the grid that encapsulates 3 columns and 3 boxes. A "puzzle" is a partially completed "grid", and the initial values are "givens" or "clues". A "proper" puzzle has a unique solution. A "minimal" puzzle is a proper puzzle from which no clue can be removed without introducing additional solutions. See Glossary of Sudoku for other terminology.
Solving Sudokus from the viewpoint of a player has been explored in Denis Berthier's book "The Hidden Logic of Sudoku" (2007) which considers strategies such as "hidden xy-chains".
Mathematical context.
The general problem of solving Sudoku puzzles on "n"2×"n"2 grids of "n"×"n" blocks is known to be NP-complete. For "n"=3 (classical Sudoku), however, this result is of little practical relevance: algorithms such as Dancing Links can solve puzzles in a fraction of a second because of the small size of the problem.
A puzzle can be expressed as a graph coloring problem. The aim is to construct a 9-coloring of a particular graph, given a partial 9-coloring. The Sudoku graph has 81 vertices, one vertex for each cell. The vertices are labeled with ordered pairs ("x", "y"), where "x" and "y" are integers between 1 and 9. In this case, two distinct vertices labeled by ("x", "y") and ("x"′, "y"′) are joined by an edge if and only if:
The puzzle is then completed by assigning an integer between 1 and 9 to each vertex, in such a way that vertices that are joined by an edge do not have the same integer assigned to them.
A Sudoku solution grid is also a Latin square. There are significantly fewer Sudoku grids than Latin squares because Sudoku imposes the additional regional constraint.
Sudokus from group tables.
As in the case of Latin squares the (addition- or) multiplication tables (Cayley tables) of finite groups can be used to construct Sudokus and related tables of numbers. Namely, one has to take subgroups and quotient groups into account:
Take for example formula_1 the group of pairs, adding each component separately modulo some formula_2.
By omitting one of the components, we suddenly find ourselves in formula_3 (and this mapping is obviously compatible with the respective additions, i.e. it is a group homomorphism).
One also says that the latter is a quotient group of the former, because some once different elements become equal in the new group.
However, it is also a subgroup, because we can simply fill the missing component with formula_4 to get back to formula_1.
Under this view, we write down the example, Grid 1, for formula_6.
Each Sudoku region looks the same on the second component (namely like the subgroup formula_7), because these are added regardless of the first one.
On the other hand, the first components are equal in each block, and if we imagine each block as one cell, these first components show the same pattern (namely the quotient group formula_7). As outlined in the article of Latin squares, this is a Latin square of order formula_9.
Now, to yield a Sudoku, let us permute the rows (or equivalently the columns) in such a way, that each block is redistributed exactly once into each block – for example order them formula_10.
This of course preserves the Latin square property. Furthermore, in each block the lines have distinct first component by construction
and each line in a block has distinct entries via the second component, because the blocks' second components originally formed a Latin square of order formula_11 (from the subgroup formula_7). Thus we arrive at a Sudoku (rename the pairs to numbers 1...9 if you wish). With the example and the row permutation above, we arrive at Grid 2.
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 formula_13 with quotient- and subgroup formula_14.
It seems clear (already from enumeration arguments), that not all Sudokus can be generated this way.
Variants.
A Sudoku can be interpreted as a tiling (or cover) of a Latin square with polyominoes (the "regions" of the Sudoku). The classic 9×9 Sudoku is made of square nonominoes. It is possible to apply the rules of Sudoku to puzzles of other sizes, although only "N"2×"N"2 Sudoku puzzles can be tiled with square polyominoes.
See the Glossary of Sudoku for an expanded list of variants.
Rectangular regions.
A popular variant is made of rectangular regions ("blocks" or "boxes") – for example, 2×3 hexominoes tiled in a 6×6 grid. The following notation is used for discussing this variant:
Sudoku with square "N"×"N" regions are more symmetrical than rectangular Sudoku since each row and column intersects "N" regions and shares "N" cells with each. The number of bands and stacks also equals "N". The "3×3" Sudoku is additionally unique: "N" is also the number of row-column-region constraints from the "One Rule" (i.e. there are "N"=3 types of "units").
Jigsaw sudokus.
A Sudoku whose regions are not (necessarily) square or rectangular is known as a Jigsaw Sudoku. In particular, an "N"×"N" square where "N" is prime can only be tiled with irregular "N"-ominoes. For small values of "N" the number of ways to tile the square (excluding symmetries) has been computed . For "N" ≥ 4 some of these tilings are not compatible with any Latin square; i.e. all Sudoku puzzles on such a tiling have no solution.
Solutions.
The answer to the question 'How many Sudoku grids are there?' depends on the definition of when similar solutions are considered different.
Ordinary Sudoku.
All 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, obtaining 6,670,903,752,021,072,936,960 () distinct solutions.
In a 2005 study, Felgenhauer and Jarvis 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.
This subsequent technique resulted in roughly needing 1/97 of the number of computation cycles as the original techniques, but was significantly more complicated to set up.
Essentially different solutions.
Validity preserving transformations.
Two valid grids are "essentially" the same if one can be derived from the other, using a so-called "validity preserving transformation (VPT)". These transformations always transform a valid grid into another valid grid. There are two major types: symbol permutations (relabeling) and cell permutations (rearrangements). They are:
and rearranging (shuffling):
These operations define a relation between equivalent grids. With respect to the 81 grid cell values, the rearranging operations form a subgroup of the symmetric group S81, of order 3!8×2 = 3,359,232. The relabeling operations are isomorphic with S9 and generate an additional 9! = 362,880 equivalent grids. Applying these operations on a grid results in 3!8×2×9! or 1,218,998,108,160 essentially equivalent grids. However, there is a small number of sudokus for which the above operations generate fewer grids; these are the self-similar, or automorphic sudokus. Only about 0.01% of all essentially unique grids are automorphic, but counting them is necessary for evaluating the exact number of essentially different sudokus.
The sudoku symmetry group.
The precise structure of the sudoku symmetry group can be expressed succinctly using the wreath product (≀). The possible row (or column) permutations form a group isomorphic to "S"3 ≀ "S"3 of order 3!4 = 1,296. The whole rearrangement group is formed by letting the transposition operation (isomorphic to "C"2) act on two copies of that group, one for the row permutations and one for the column permutations. This is "S"3 ≀ "S"3 ≀ "C"2, a group of order 1,2962 × 2 = 3,359,232. Finally, the relabelling operations commute with the rearrangement operations, so the full sudoku (VPT) group is ("S"3 ≀ "S"3 ≀ "C"2) × "S"9 of order 1,218,998,108,160.
Fixed points and Burnside's lemma.
The set of equivalent grids which can be reached using these operations (excluding relabeling) forms an orbit of grids under the action of the rearrangement 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 grids that either do not change under the rearrangement operation or only differ by relabeling. To simplify the calculation the elements of the rearrangement group are sorted into conjugacy classes, whose elements all have the same number of fixed points. It turns out only 27 of the 275 conjugacy classes of the rearrangement group have fixed points; these conjugacy classes represent the different types of symmetry (self-similarity or automorphism) that can be found in completed sudoku grids. Using this technique, Ed Russell and Frazer Jarvis were the first to compute the number of essentially different sudoku solutions as 5,472,730,538.
Note that a grid may be a fixed point of several transformations simultaneously; for example, any grid which has a quarter-turn symmetry also has half-turn symmetry. The combination of all transformations that fix a particular grid is the stabilizer subgroup ("automorphism group") of that grid.
Stabilizer subgroups.
Russell has compiled a list of 122 "essentially different" non-trivial stabilizer subgroup conjugacy classes ("automorphism groups"), along with an example grid, the VPT conjugacy classes in the group, a set of generators and the number of essentially different grids (orbits) with that stabilizer class. Up to isomorphism there are 26 different group structures. There are 15 different possible stabilizer group sizes, listed in the next section.
Number of essentially equivalent grids.
Each of the essentially unique grids can be analyzed for self-similarities ("automorphisms") to evaluate the 'deficiency' in the number of essentially equivalent grids. The results are summarized in the table below. In total 560,151 of the 5,472,730,538 essentially unique grids (about 0,01%) have a form of self-similarity (a non-trivial stabilizer).
The size of the orbit (that is, number of essentially equivalent grids) can be calculated using the orbit-stabilizer theorem: it is the size of the sudoku symmetry group divided by the size of the stabilizer (or "automorphism") group. Multipling the number of essentially unique grids (the number of orbits) with the orbit size gives the total number of grids with that stabilizer group size; summation then once again provides the total number of possible sudoku grids. "Automorphic" grids have smaller orbits so the probability that a random grid has a symmetry drops: from about 1 in 10,000 for essentially different grids to about 1 in 20,000 for all grids.
Other variants.
Enumeration results for many Sudoku variants have been calculated: these are summarised below.
Sudoku with additional constraints.
The following are all restrictions of the classic 3×3 Sudoku (9×9 grid). The type names have not been standardised: click on the attribution links to see the definitions. The ordinary Sudoku is included in the last row for comparison.
Sudoku with rectangular regions.
In the table, block dimensions are those of the regions (e.g. 3×3 in normal Sudoku). The "Rel Err" column indicates how a simple approximation based on calculated band counts (detailed in the sections below) compares to the true grid count: it is an underestimate in all cases evaluated so far. The numbers for square block grids ("n"2 × "n"2) are listed in , and the numbers for 2 × "n" blocks (2"n" × 2"n" grids) are listed in .
Similar to Latin squares, the number of sudoku grids can be "reduced" by noting that there is a one-to-one correspondence with a partially standardized form, in which the first block has the canonical labels and both the top row and leftmost column are sorted (for as much as the rules allow, i.e. within blocks and the stacks/bands themselves). For a grid with blocks, each such reduced grid corresponds to formula_15total grids, which is 9! × 722 or 1,881,169,920 for the normal 3×3 Sudoku. This reduction is always one-to-one, unlike the action of the full set of validity preserving transformations ('Sudoku symmetries') discussed below.
A solved Sudoku will remain valid under the actions of the validity preserving transformations (see also Jarvis). By carefully counting the number of invariant grids for each transformation one can compute the number of essentially different Sudoku grids (see above). Similar methods have been applied to sudoku grids of other dimensions; the results are summarized in the table below. For square block grids the transposition transformation may or may not (see below) be included in the VPT (symmetry) group. The number of essentially different grids can be estimated by dividing the total number of grids (either known or estimated) by the size of the VPT group (which is easily computed), which essentially assumes the number of automorphic sudokus is negligible. The numbers for 2 × "n" blocks (2"n" × 2"n" grids) are listed in .
Estimation method.
The method of Kevin Kilfoil (generalised by Pettersen) can be used to estimate the number of completed grids using the number of possible completed bands and stacks. The method asserts that the Sudoku row and column constraints are, to first approximation, conditionally independent given the box constraint. This gives the Kilfoil-Silver-Pettersen formula:
where formula_17 is the number of ways of filling a "R"×"RC" band of "R" horizontally adjacent "R"×"C" boxes (equivalently, formula_18 is the number of ways of filling a "RC"×"C" stack of "C" vertically adjacent "R"×"C" boxes), and the denominator ("RC")!"RC" is the number of ways to fill the grid while satisfying only the box contraints.
As explained by Pettersen: "This is how: Let be the space of -grids built by legal sudoku bands, but with no attention put on whether the columns follow the rules of Sudoku. The size of is . Let also be the set of grids built by legal stacks with no attention put on the rows, is then . The nxm-sudoku grids are then the intersection of and . A random and are identical in a given box with probability , and under the assumption that these probabilities are independent for each box, we arrive at the estimate above."
This estimation has proven to be accurate to about 0.2% for the classical 9×9 grid, and within 1% for larger grids for which exact values are known (see table above).
Number of bands.
Exact formulae for the number of possible bands formula_17 in a filled sudoku grid with blocks of size "R"×"C" are known:
Several known band counts are listed below. Petersen's algorithm, as implemented and improved by Silver, splits the band into subbands, which are then grouped into equivalence classes; it is currently the fastest known technique for exact evaluation of these "b"R,C.
Puzzles.
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.
Many Sudokus have been found with 17 clues, although finding them is not a trivial task. 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, and this was independently confirmed in September 2013. 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. 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. 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.
A Sudoku with 24 clues, dihedral symmetry (symmetry on both orthogonal axis, 90° rotational symmetry, 180° rotational symmetry, and diagonal symmetry) is known to exist, and is also automorphic. Again here, it is not known if this number of clues is minimal for this class of Sudoku. The fewest clues in a Sudoku with two-way diagonal symmetry is believed to be 18, and in at least one case such a Sudoku also exhibits automorphism.
Among the 5,472,730,538 essentially different solution grids, only 4 don't have a 20 clue puzzle - those 4 grids do have a 21-clue puzzle.
Sudoku with additional constraints.
Additional constraints (here, on 3×3 Sudokus) lead to a smaller minimum number of clues.
Sudoku with irregular regions.
"Du-sum-oh" (a.k.a. "geometry number place") puzzles replace the 3×3 (or "R"×"C") regions of Sudoku with irregular shapes of a fixed size. Bob Harris has proved that it is always possible to create ("N" − 1)-clue du-sum-ohs on an "N"×"N" grid, and has constructed several examples. Johan de Ruiter has proved that for any "N">3 there exist polyomino tilings that can not be turned into a Sudoku puzzle with "N" irregular shapes of size "N".
Sum number place ("Killer Sudoku").
In sum number place (Samunampure), the regions are of irregular shape and various sizes. The usual constraints of no repeated value in any row, column or region apply. The clues are given as sums of values within regions (e.g. a 4-cell region with sum 10 must consist of values 1,2,3,4 in some order). The minimum number of clues for Samunampure is not known, nor even conjectured. A variant on Miyuki Misawa's web site replaces sums with relations: the clues are symbols =, < and > showing the relative values of (some but not all) adjacent region sums. She demonstrates an example with only eight relations. It is not known whether this is the best possible.
Maximum number of givens.
The most clues for a "minimal" Sudoku is believed to be 40, of which only two are known. If any clue is removed from either of these Sudokus, the puzzle would have more than one solution (and thus not be a proper Sudoku). In the work to find these Sudokus, other high-clue puzzles were catalogued, including more than 6,500,000,000 minimal puzzles with 36 clues. About 2600 minimal Sudokus with 39 clues were also found.
If dropping the requirement for the uniqueness of the solution, 41-clue minimal pseudo-puzzles are known to exist, but they can be completed to more than one solution grid. Removal of any clue increases the number of the completions and from this perspective none of the 41 clues is redundant. With slightly more than half the grid filled with givens (41 of 81 cells), the "uniqueness" of the solution constraint still dominates over the "minimality" constraint.
As for the "most" clues possible in a Sudoku while still "not" rendering a unique solution, it is four short of a full grid (77). If two instances of two numbers each are missing and the cells they are to occupy are the corners of an orthogonal rectangle, and exactly two of these cells are within one region, there are two ways the last digits can be added (two solutions).
Number of minimal puzzles.
The number of minimal Sudokus (Sudokus in which no clue can be deleted without losing uniqueness of the solution) is not precisely known. However, statistical techniques combined with a generator (), show that there are approximately (with 0.065% relative error):
Other authors used faster methods and calculated additional precise distribution statistics.
Constraints of clue geometry.
It has been conjectured that no proper Sudoku can have clues limited to the range of positions in the pattern above (first image). The largest rectangular orthogonal "hole" (region with no clues) in a proper Sudoku is believed to be a rectangle of 30 cells (a 5×6 rectangular area). One example is a Sudoku with 22 clues (second image). The largest total number of empty groups (rows, columns, and boxes) in a Sudoku is believed to be nine. One example is a Sudoku with 3 empty rows, 3 empty columns, and 3 empty boxes (third image).
Automorphic Sudokus.
A Sudoku grid is automorphic if it can be transformed in a way that leads back to the original grid, when that same transformation would not otherwise lead back to the original grid. One example of a grid which is automorphic would be a grid which can be rotated 180 degrees resulting in a new grid where the new cell values are a permutation of the original grid. Automorphic Sudokus are Sudoku puzzles which solve to an automorphic grid. Two examples of automorphic Sudokus, and an automorphic grid are shown below.
In the first two examples, notice that if the Sudoku is rotated 180 degrees, and the clues relabeled with the permutation (123456789) -> (987654321), it returns to the same Sudoku. Expressed another way, these Sudokus have the property that every 180-degree rotational pair of clues (a, b) follows the rule (a) + (b) = 10.
Since these Sudokus are automorphic, so too their solutions grids are automorphic. Furthermore, every cell which is solved has a symmetrical partner which is solved with the same technique (and the pair would take the form a + b = 10). Notice that in the second example, the Sudoku also exhibits translational (or repetition) symmetry; clues are clustered in groups, with the clues in each group ordered sequentially (i.e., n, n+1, n+2, and n+3).
The third image is the "Most Canonical" solution grid. This grid has 648 automorphisms and contributes to all ~ solution grids by factor of 1/648 compared to any non-automorphic grid.
In these examples the automorphisms are easy to identify, but in general automorphism is not always obvious. The table at right shows the number of the essentially different Sudoku solution grids for all existing automorphisms.
Details of enumerating distinct grids (9×9).
An enumeration technique based on "band generation" was developed that is significantly less computationally intensive. The strategy begins by analyzing the permutations of the top band used in valid solutions. Once the Band1 symmetries and equivalence class for the partial solutions are identified, the completions of the lower two bands are constructed and counted for each equivalence class.
Counting the top band permutations.
The Band1 algorithm proceeds as follows: