Mathematics of Sudoku
The analysis of Sudoku is generally divided between analyzing the properties of unsolved puzzles (such as the minimum possible number of given clues) and analyzing the properties of solved puzzles.
Initial analysis was largely focused on enumerating solutions, with results first appearing in 2004.
[1] For classical Sudoku, the number of filled grids is 6,670,903,752,021,072,936,960 (6.671×1021), which reduces to 5,472,730,538 essentially different solutions under the validity-preserving transformations.
The largest minimal puzzle found so far has 40 clues in the 81 cells.
Ordinary Sudokus (proper puzzles) have a unique solution.
This section discusses the minimum number of givens for proper puzzles.
Many Sudokus have been found with 17 clues, although finding them is not a trivial task.
[2][3] 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.
However, statistical techniques combined with a generator ('Unbiased Statistics of a CSP – A Controlled-Bias Generator'),[6] show that there are approximately (with 0.065% relative error): 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).
Other variants include those with irregularly-shaped regions or with additional constraints (hypercube).
A puzzle is a partially completed grid, and the initial values are givens or clues.
Solving Sudokus from the viewpoint of a player has been explored in Denis Berthier's book "The Hidden Logic of Sudoku" (2007)[7] which considers strategies such as "hidden xy-chains".
The general problem of solving Sudoku puzzles on n2×n2 grids of n×n blocks is known to be NP-complete.
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.
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.
For small values of N the number of ways to tile the square (excluding symmetries) has been computed (sequence A172477 in the OEIS).
Symmetries play a significant role in the enumeration strategy, but not in the count of all possible solutions.
In a 2005 study, Felgenhauer and Jarvis[13][12] analyzed the permutations of the top band used in valid solutions.
A second enumeration technique based on band generation was later developed that is significantly less computationally intensive.
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 S3 ≀ S3 of order 3!4 = 1,296.
The Burnside fixed points are grids that either do not change under the rearrangement operation or only differ by relabeling.
It turns out only 27 of the 275 conjugacy classes of the rearrangement group have fixed points;[14] 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.
[14][15] Excluding relabeling, the operations of the sudoku symmetry group all consist of cell rearrangements which are solution-preserving, raising the question of whether all such solution-preserving cell rearrangements are in the symmetry group.
