Mathematics of Sudoku

This article is about the mathematical analysis of Sudoku puzzles. For solving and generating algorithms, see Sudoku solving algorithms.

A 24-clue automorphic Sudoku with translational symmetry

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×10²¹), 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

See also: Glossary of Sudoku § 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 (hypercube).

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

A Sudoku with 18 clues and orthogonal symmetry

A Sudoku with 24 clues and complete geometric symmetry

A Sudoku with 19 clues and two-way orthogonal symmetry

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 (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 n²×n² grids of n×n blocks has a solution is known to be NP-complete.

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:

• a single square of the puzzle,
• a pair of a digit value and a row,
• a pair of a digit value and a column, or
• a pair of a digit value and a box.

Each choice to place a digit in a square can be encoded as a set of four of these elements, one of each kind: the square the digit is placed in, and the pair of the digit value with the row, column, and box of the square. This encoding produces a family of 9⁶ = 531441 four-element sets, one for each placement of a digit in a square. There are 81 elements of each kind, for a total of 324 elements. An exact cover for this set system provides a system of choices that uses each square once and provides each digit in each row, column, and box of the puzzle. Although exact cover is also an NP-complete problem, it can often be solved in practice by methods that include the dancing links algorithm.

Number of solved grids

The answer to the question 'How many Sudoku grids are there?' depends on the definition of when similar solutions are considered different

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.

For standard $9\times 9$ Sudoku, the number of solutions is

6,670,903,752,021,072,936,960.

For $n^{2}\times n^{2}$ Sudoku puzzles (where $n=3$ for ordinary $9\times 9$ Sudoku), no closed-form formula is known for the number of solutions, but an asymptotic formula is known, analogous to Stirling's approximation for the number of permutations. According to this formula, the number of solutions is $$\left({\frac {n^{2}}{e^{3}}}+o(n^{2})\right)^{n^{4}}.$$ Here, the $o(n^{2})$ term uses little o notation.

The Sudoku symmetry group

The following transformations can be applied to any solved or unsolved Sudoku puzzle, preserving the validity of a solved puzzle and the unique solvability of an unsolved one:

• Arbitrarily relabelling the nine digits of the puzzle
• Arbitrarily rearranging any three consecutive rows belonging to the same boxes
• Arbitrarily rearranging the three sets of three consecutive rows
• Arbitrarily rearranging any three consecutive columns belonging to the same boxes
• Arbitrarily rearranging the three sets of three consecutive columns
• Reflecting the puzzle along a diagonal, swapping rows for columns and vice versa

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}\wr S_{3}$ of order 3!⁴ = 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}\wr S_{3}\wr C_{2}$, a group of order 1,296² × 2 = 3,359,232. Finally, the relabelling operations commute with the rearrangement operations, so the full sudoku (VPT) group is $(S_{3}\wr S_{3}\wr C_{2})\times S_{9}$ of order 1,218,998,108,160.

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. In 2008, Aviv Adler and Ilan Adler showed that all solution-preserving cell rearrangements are contained in the group, even for general $n^{2}\times n^{2}$ grids.

Essentially different solutions

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.

See also

• Sudoku code