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 (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. 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. 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.
Terminology Regions of the Sudoku 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.
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 (sequence A172477 in the OEIS). 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.
Other variants
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.
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 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. The digits used in the clues are also constrained: the givens of a proper puzzle must include at least eight of the nine digits, since two digits absent from the clues could be interchanged throughout a solution to yield a second one. More generally, a proper n2×n2 puzzle must use at least n2 − 1 distinct digits among its givens.
Symmetrical Sudoku The fewest clues in a Sudoku with two-way diagonal symmetry (a 180° rotational 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 (a 90° rotational symmetry, which also includes a symmetry on both orthogonal axis, 180° rotational symmetry, and diagonal symmetry) is known to exist, but it is not known if this number of clues is minimal for this class of Sudoku.
Computational complexity The general problem of determining whether a Sudoku puzzle on n2×n2 grids of n×n blocks has a solution is known to be NP-complete. The result is closely related to Colbourn's earlier theorem that completing a partial Latin square is NP-complete, since a Sudoku solution grid is a Latin square subject to an additional constraint on its blocks; hardness also holds for restricted classes of clue pattern. A related problem is the another solution problem (ASP): given an instance together with one solution, decide whether a second, distinct solution exists. Sudoku is ASP-complete under parsimonious reduction. This is the form of the problem that governs puzzle construction rather than puzzle solving, since a puzzle is proper exactly when the corresponding ASP instance has no second solution. A puzzle can be expressed as a special case of the precoloring extension problem, a variation of graph coloring with some graph vertices already starting with assigned colors. 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:
x = x′ (same column) or, y = y′ (same row) or, ⌈ x/3 ⌉ = ⌈ x′/3 ⌉ and ⌈ y/3 ⌉ = ⌈ y′/3 ⌉ (same 3×3 cell) 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. Another way of formulating Sudoku as a computational problem is as the exact cover problem. In this problem, one is given a family of sets, and must choose a subfamily of disjoint sets that has the same union. One way of formulating a Sudoku puzzle in this way uses sets with four kinds of elements:
… excerpt ends here. Continue reading the full article.
