Mathematics of Sudoku
Mathematics can be used to study Sudoku puzzles 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 analysis of Sudoku is generally divided between analyzing the properties of unsolved puzzles and analyzing the properties of solved puzzles. Initial analysis was largely focused on enumerating solutions, with results first appearing in 2004.
For 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 solutions] under the validity-preserving transformations. There are 26 possible types of symmetry, but they can only be found in about 0.005% of all filled grids. An ordinary puzzle with a unique solution must have at least 17 clues. There is a solvable puzzle with at most 21 clues for every solved grid. The largest minimal puzzle found so far has 40 clues in the 81 cells.
Puzzles
Minimum number of givens
Ordinary Sudokus 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 2014 paper by Gary McGuire, Bastian Tugemann, and Gilles Civario proved that the minimum number of clues in any proper Sudoku is 17 through an exhaustive computer search based on hitting set enumeration.Symmetrical 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. A Sudoku with 24 clues, dihedral symmetry is known to exist, but it is not known if this number of clues is minimal for this class of Sudoku.Total number of minimal puzzles
The number of minimal Sudokus is not precisely known. However, statistical techniques combined with a generator, show that there are approximately :- 3.10 × 1037 distinct minimal puzzles,
- 2.55 × 1025 minimal puzzles that are not pseudo-equivalent.
Variants
There are many Sudoku variants, partially characterized by size, and the shape of their regions. Unless noted, discussion in this article assumes classic Sudoku, i.e. N=9. A rectangular Sudoku uses rectangular regions of row-column dimension R×''C. Other variants include those with irregularly-shaped regions or with additional constraints.Regions are also called blocks or boxes. A band is a part of the grid that encapsulates three rows and three boxes, and a stack is a part of the grid that encapsulates three columns and three 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.
Solving Sudokus from the viewpoint of a player has been explored in Denis Berthier's book "The Hidden Logic of Sudoku" which considers strategies such as "hidden xy-chains".
Mathematical context
The general problem of solving Sudoku puzzles on n2×n2 grids of n×''n blocks is known to be NP-complete.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, where x'' and y are integers between 1 and 9. In this case, two distinct vertices labeled by and are joined by an edge if and only if:x = x′ or,y = y′ or,
- ⌈ x/3 ⌉ = ⌈ x′/3 ⌉ and ⌈ y/3 ⌉ = ⌈ y′/3 ⌉
A Sudoku solution grid is also a Latin square. There are significantly fewer Sudoku grids than Latin squares because Sudoku imposes additional regional constraints.
Sudokus from group tables
As in the case of Latin squares the multiplication 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 the group of pairs, adding each component separately modulo some.
By omitting one of the components, we suddenly find ourselves in .
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 to get back to.
Under this view, we write down the example, Grid 1, for.
Each Sudoku region looks the same on the second component, 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. As outlined in the article of Latin squares, this is a Latin square of order.
Now, to yield a Sudoku, let us permute the rows in such a way, that each block is redistributed exactly once into each block – for example order them.
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 . Thus we arrive at a Sudoku. 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 with quotient- and subgroup.
It seems clear, that not all Sudokus can be generated this way.
Jigsaw sudokus
A Sudoku whose regions are not 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 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 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 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.