TheInfoList

OR:

The mathematics of Sudoku refers to the use of
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
to study
Sudoku Sudoku (; ja, 数独, sūdoku, digit-single; originally called Number Place) is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row ...
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 Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
and
group theory In abstract algebra, group theory studies the algebraic structures known as groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces, can all be seen a ...
. The analysis of Sudoku falls 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 (), which reduces to 5,472,730,538 essentially different solutions under the validity preserving transformations. There are 26 types of
symmetry Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
, 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.

# 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.G. McGuire, B. Tugemann, G. Civario
"There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem"
Arxiv.org.
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. 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 In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphis ...
.

### Sudokus of other sizes

* 6×6(2×3) Sudoku: The fewest clues is 8.
Minimal number of clues for Sudokus
* 8×8(2×4) Sudoku: The fewest clues is 14.

## 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): * 3.10 × 1037 minimal puzzles, * 2.55 × 1025 non-essentially-equivalent minimal puzzles.

# Variants

There are many Sudokian, 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 In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, per ...
). 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 In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
. A puzzle can be expressed as a
graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...
problem.Lewis, R. ''A Guide to Graph Colouring: Algorithms and Applications''. Springer International Publishers, 2015. 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 In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bico ...
: * ''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. A Sudoku solution grid is also a
Latin square In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin s ...
. 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 square In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin s ...
multiplication table In mathematics, a multiplication table (sometimes, less formally, a times table) is a mathematical table used to define a multiplication operation for an algebraic system. The decimal multiplication table was traditionally taught as an ess ...
s (
Cayley table Named after the 19th century British mathematician Arthur Cayley, a Cayley table describes the structure of a finite group by arranging all the possible products of all the group's elements in a square table reminiscent of an addition or multiplic ...
s) of finite groups can be used to construct Sudokus and related tables of numbers. Namely, one has to take
subgroup In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgro ...
s and
quotient group A quotient group or factor group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure (the rest of the structure is "factored" out). For exam ...
s into account: Take for example $\mathbb_\oplus\mathbb_$ the group of pairs, adding each component separately modulo some $n$. By omitting one of the components, we suddenly find ourselves in $\mathbb_$ (and this mapping is obviously compatible with the respective additions, i.e. it is a
group homomorphism In mathematics, given two groups, (''G'', ∗) and (''H'', ·), a group homomorphism from (''G'', ∗) to (''H'', ·) is a function ''h'' : ''G'' → ''H'' such that for all ''u'' and ''v'' in ''G'' it holds that : h(u*v) = h(u) \cdot h(v) ...
). One also says that the latter is a
quotient group A quotient group or factor group is a mathematical group obtained by aggregating similar elements of a larger group using an equivalence relation that preserves some of the group structure (the rest of the structure is "factored" out). For exam ...
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 $0$ to get back to $\mathbb_\oplus\mathbb_$. Under this view, we write down the example, Grid 1, for $n=3$. Each Sudoku region looks the same on the second component (namely like the subgroup $\mathbb_$), 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 $\mathbb_$). As outlined in the article of Latin squares, this is a Latin square of order $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 $1,4,7,2,5,8,3,6,9$. 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 $3$ (from the subgroup $\mathbb_$). 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 An exact sequence is a sequence of morphisms between objects (for example, groups, rings, modules, and, more generally, objects of an abelian category) such that the image of one morphism equals the kernel of the next. Definition In the conte ...
of finite groups of appropriate size already does the job. Try for example the group $\mathbb_$ with quotient- and subgroup $\mathbb_$. It seems clear (already from enumeration arguments), that not all Sudokus can be generated this way.

### 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 A Usenet newsgroup is a repository usually within the Usenet system, for messages posted from users in different locations using the Internet. They are discussion groups and are not devoted to publishing news. Newsgroups are technically distin ...
in 2003, obtaining 6,670,903,752,021,072,936,960 () distinct solutions. In a 2005 study, Felgenhauer and Jarvis. analyzed the
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, ...
s of the top band used in valid solutions. Once the Band1
symmetries Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
and
equivalence class In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
es 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.

### = The sudoku symmetry group

= The precise structure of the sudoku symmetry
group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
can be expressed succinctly using the
wreath product In group theory, the wreath product is a special combination of two groups based on the semidirect product. It is formed by the action of one group on many copies of another group, somewhat analogous to exponentiation. Wreath products are used ...
(≀). The possible row (or column) permutations form a group
isomorphic In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
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 In celestial mechanics, an orbit is the curved trajectory of an object such as the trajectory of a planet around a star, or of a natural satellite around a planet, or of an artificial satellite around an object or position in space such ...
of grids under the action of the rearrangement
group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
. 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 class In mathematics, especially group theory, two elements a and b of a group are conjugate if there is an element g in the group such that b = gag^. This is an equivalence relation whose equivalence classes are called conjugacy classes. In other ...
es, 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.

*
Combinatorial explosion In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to how the combinatorics of the problem is affected by the input, constraints, and bounds of the problem. Combinatorial explosion is sometimes used to ...
(with summary of grid count of Sudoku compared to Latin squares) * Dancing Links * Glossary of Sudoku * Sudokian * Sudoku code

*