View source for Mathematics of Sudoku

{{short description|Mathematical investigation of Sudoku}}
{{about|the mathematical analysis of Sudoku puzzles|solving and generating algorithms|Sudoku solving algorithms}}
{{Unreliable sources|date=May 2024}}
{{Use dmy dates|date=January 2020}}
[[File:Sudoku_Puzzle_(automorphic_with_translational_symmetry).png|thumb|upright=1.2|right|alt=A 24-clue automorphic sudoku with translational symmetry.|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.<ref>{{citation |last=Lin |first=Keh Ying |title=Number of Sudokus |journal= Journal of Recreational Mathematics |volume=33 |issue=2 |year=2004 |pages=120–24}}.</ref>

For classical Sudoku, the number of filled grids is '''6,670,903,752,021,072,936,960''' ({{val|6.671|e=21}}), which reduces to '''5,472,730,538''' [[#Essentially different solutions|essentially different solutions]] under the validity-preserving transformations. There are 26 possible types of [[Symmetry in mathematics|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==
==={{anchor|Sudokus with few clues}}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====
{| align="right" border="0" cellpadding="1" cellspacing="0"
 |-valign="top"
 |
[[File:Oceans_Sudoku17_Puzzle-39451_trimmed.png|thumb|180px|A Sudoku with 17 clues]]
 |
[[File:Sudoku Puzzle (a symmetrical puzzle with 17 clues) R4.png|thumb|180px|A Sudoku with 17 clues and diagonal symmetry]]
 |
[[File:Sudoku (18 clue symmetrical).png|thumb|180px|A Sudoku with 18 clues and orthogonal symmetry]]
|}
{| align="right" border="0" cellpadding="1" cellspacing="0"
|-valign="top"
|
[[File:Sudoku_Puzzle_(a_puzzle_with_total_symmetry)_trimmed.png|thumb|180px|A Sudoku with 24 clues and complete geometric symmetry]]
|
[[File:Sudoku_Puzzle_(Tourmaline)R2.png|thumb|180px|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.<ref>{{cite web |url=http://www2.ic-net.or.jp/~takaken/auto/guest/bbs46.html |title=プログラミングパズル雑談コーナー |publisher=.ic-net.or.jp |access-date=20 October 2013 |archive-date=12 October 2016 |archive-url=https://web.archive.org/web/20161012180015/http://www2.ic-net.or.jp/~takaken/auto/guest/bbs46.html |url-status=dead }}</ref><ref name="sudokumin">{{cite web |url=http://www.csse.uwa.edu.au/~gordon/sudokumin.php |title=Minimum Sudoku |publisher=Csse.uwa.edu.au |access-date=20 October 2013 |archive-date=26 November 2006 |archive-url=https://web.archive.org/web/20061126162713/http://www.csse.uwa.edu.au/~gordon/sudokumin.php |url-status=dead }}</ref> 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 [[monotone dualization|hitting set enumeration]].<ref name=":3">{{cite journal |first1=G. |last1=McGuire |first2=B. |last2=Tugemann |first3=G. |last3=Civario |pages=190–217 |year=2014 |doi=10.1080/10586458.2013.870056 |title=There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem |journal=Experimental Mathematics |volume=23 |issue=2 |arxiv=1201.0749}}</ref>

====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 group|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.<ref>
{{citation
 | last = Taalman | first = Laura | author-link = Laura Taalman
 | issue = 1
 | journal = Math Horizons
 | jstor = 25678701
 | pages = 5–9
 | title = Taking Sudoku seriously
 | volume = 15
 | year = 2007| doi = 10.1080/10724117.2007.11974720 | s2cid = 126371771}}. See in particular Figure&nbsp;7, p.&nbsp;7.</ref>

=== Total 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 ({{lang|en|'Unbiased Statistics of a CSP – A Controlled-Bias Generator'}}),<ref name="Unbiased Statistics of a CSP - A Controlled-Bias Generator">{{cite news|last=Berthier|first=Denis|date=4 December 2009|title=Unbiased Statistics of a CSP – A Controlled-Bias Generator|url=http://hal.archives-ouvertes.fr/hal-00641955|access-date=4 December 2009}}</ref> show that there are approximately (with 0.065% relative error):
* 3.10&nbsp;×&nbsp;10<sup>37</sup> distinct minimal puzzles,
* 2.55&nbsp;×&nbsp;10<sup>25</sup> minimal puzzles that are not pseudo-equivalent (i.e. same arrangement where all instances of one digit is switched with another digit).

==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 ([[#Sudoku with additional constraints|hypercube]]).

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" (2007)<ref>{{cite book |first = Denis |last = Berthier |date = November 2007 |title = The Hidden Logic of Sudoku |edition = Second, revised and extended |isbn =  978-1847534729 |publisher = Lulu.com}}</ref> which considers strategies such as "hidden xy-chains".

===Mathematical context===
The general problem of solving Sudoku puzzles on ''n''<sup>2</sup>×''n''<sup>2</sup> grids of ''n''×''n'' blocks is known to be [[NP-complete]].<ref>{{Cite journal |last1=Yato |first1=Takayuki |last2=Seta |first2=Takahiro |date=2003 |title=Complexity and Completeness of Finding Another Solution and Its Application to Puzzles |journal=IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences |volume=E86-A |issue=5 |pages=1052–1060}}</ref>

A puzzle can be expressed as a [[graph coloring]] problem.<ref name="Lewis2015">Lewis, R. ''A Guide to Graph Colouring: Algorithms and Applications''. Springer International Publishers, 2015.</ref> 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.

A Sudoku solution grid is also a [[Latin square]].<ref name="Lewis2015" /> 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 square]]s the (addition- or) [[multiplication table]]s ([[Cayley table]]s) of finite groups can be used to construct Sudokus and related tables of numbers. Namely, one has to take [[subgroup]]s and [[quotient group]]s into account:

Take for example <math>\mathbb{Z}_{n}\oplus\mathbb{Z}_{n}</math> the group of pairs, adding each component separately modulo some <math>n</math>.
By omitting one of the components, we suddenly find ourselves in <math>\mathbb{Z}_{n}</math> (and this mapping is obviously compatible with the respective additions, i.e. it is a [[group homomorphism]]).
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 <math>0</math> to get back to <math>\mathbb{Z}_{n}\oplus\mathbb{Z}_{n}</math>.

Under this view, we write down the example, '''Grid 1''', for <math>n=3</math>.

Each Sudoku region looks the same on the second component (namely like the subgroup <math>\mathbb{Z}_{3}</math>), 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 <math>\mathbb{Z}_{3}</math>). As outlined in the article of Latin squares, this is a Latin square of order <math>9</math>.

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 <math>1,4,7,2,5,8,3,6,9</math>.
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 <math>3</math> (from the subgroup <math>\mathbb{Z}_{3}</math>). 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'''.
{|  style="border-spacing: 10px"
|-
|{{Sudoku 9x9 grid|title='''Grid 1''' – The addition table in <math>\mathbb{Z}_{3}\oplus\mathbb{Z}_{3}</math>|align=center|cellsize=24pt
|s1=(0,0) |s2=(0,1) |s3=(0,2) |s4=(1,0) |s5=(1,1) |s6=(1,2) |s7=(2,0) |s8=(2,1) |s9=(2,2) 
|s10=(0,1)|s11=(0,2)|s12=(0,0)|s13=(1,1)|s14=(1,2)|s15=(1,0)|s16=(2,1)|s17=(2,2)|s18=(2,0)
|s19=(0,2)|s20=(0,0)|s21=(0,1)|s22=(1,2)|s23=(1,0)|s24=(1,1)|s25=(2,2)|s26=(2,0)|s27=(2,1)
|s28=(1,0)|s29=(1,1)|s30=(1,2)|s31=(2,0)|s32=(2,1)|s33=(2,2)|s34=(0,0)|s35=(0,1)|s36=(0,2)
|s37=(1,1)|s38=(1,2)|s39=(1,0)|s40=(2,1)|s41=(2,2)|s42=(2,0)|s43=(0,1)|s44=(0,2)|s45=(0,0)
|s46=(1,2)|s47=(1,0)|s48=(1,1)|s49=(2,2)|s50=(2,0)|s51=(2,1)|s52=(0,2)|s53=(0,0)|s54=(0,1)
|s55=(2,0)|s56=(2,1)|s57=(2,2)|s58=(0,0)|s59=(0,1)|s60=(0,2)|s61=(1,0)|s62=(1,1)|s63=(1,2)
|s64=(2,1)|s65=(2,2)|s66=(2,0)|s67=(0,1)|s68=(0,2)|s69=(0,0)|s70=(1,1)|s71=(1,2)|s72=(1,0)
|s73=(2,2)|s74=(2,0)|s75=(2,1)|s76=(0,2)|s77=(0,0)|s78=(0,1)|s79=(1,2)|s80=(1,0)|s81=(1,1)
|c55=yellow|c56=yellow|c57=yellow|c64=yellow|c65=yellow|c66=yellow
|c73=yellow|c74=yellow|c75=yellow
}}
|{{Sudoku 9x9 grid|title='''Grid 2''' – Generating a Sudoku|align=center|cellsize=24pt
|s1=(0,0) |s2=(0,1) |s3=(0,2) |s4=(1,0) |s5=(1,1) |s6=(1,2) |s7=(2,0) |s8=(2,1) |s9=(2,2) 
|s10=(1,0)|s11=(1,1)|s12=(1,2)|s13=(2,0)|s14=(2,1)|s15=(2,2)|s16=(0,0)|s17=(0,1)|s18=(0,2)
|s19=(2,0)|s20=(2,1)|s21=(2,2)|s22=(0,0)|s23=(0,1)|s24=(0,2)|s25=(1,0)|s26=(1,1)|s27=(1,2)
|s28=(0,1)|s29=(0,2)|s30=(0,0)|s31=(1,1)|s32=(1,2)|s33=(1,0)|s34=(2,1)|s35=(2,2)|s36=(2,0)
|s37=(1,1)|s38=(1,2)|s39=(1,0)|s40=(2,1)|s41=(2,2)|s42=(2,0)|s43=(0,1)|s44=(0,2)|s45=(0,0)
|s46=(2,1)|s47=(2,2)|s48=(2,0)|s49=(0,1)|s50=(0,2)|s51=(0,0)|s52=(1,1)|s53=(1,2)|s54=(1,0)
|s55=(0,2)|s56=(0,0)|s57=(0,1)|s58=(1,2)|s59=(1,0) |s60=(1,1)|s61=(2,2)|s62=(2,0)|s63=(2,1)
|s64=(1,2)|s65=(1,0)|s66=(1,1)|s67=(2,2)|s68=(2,0)|s69=(2,1)|s70=(0,2)|s71=(0,0)|s72=(0,1)
|s73=(2,2)|s74=(2,0)|s75=(2,1)|s76=(0,2)|s77=(0,0)|s78=(0,1)|s79=(1,2)|s80=(1,0)|s81=(1,1)
|c19=yellow|c20=yellow|c21=yellow|c46=yellow|c47=yellow|c48=yellow
|c73=yellow|c74=yellow|c75=yellow
}}
|}
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 <math>\mathbb{Z}_{4}</math> with quotient- and subgroup <math>\mathbb{Z}_{2}</math>.
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 [[Polyomino|''N''-ominoes]]. For small values of ''N'' the number of ways to tile the square (excluding symmetries) has been computed {{OEIS|A172477}}.<ref name=":16">{{Cite web|last=de Ruiter|first=Johan|date=March 15, 2010|title=On Jigsaw Sudoku Puzzles and Related Topics (Bachelor Thesis)|url=http://liacs.leidenuniv.nl/assets/Bachelorscripties/10-04-JohandeRuiter.pdf|website=Leiden Institute of Advanced Computer Science (LIACS)}}</ref> 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.<ref name=":16" />

==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]] in 2003,<ref name=":15">{{cite web|last=QSCGZ (Guenter Stertenbrink)|date=Sep 21, 2003|title=combinatorial question on 9x9 (rec.puzzles)|url=https://groups.google.com/forum/#!topic/rec.puzzles/A7pi7S12oFI|access-date=20 October 2013|website=Google Discussiegroepen}}</ref><ref name="afj2">{{cite web|last=Jarvis|first=Frazer|date=2 Feb 2008|title=Sudoku enumeration problems|url=http://www.afjarvis.org.uk/sudoku|access-date=20 October 2013|website=Frazer Jarvis's home page|publisher=University of Sheffield}}</ref> obtaining '''6,670,903,752,021,072,936,960''' ({{val|6.67|e=21}}) distinct solutions.

In a 2005 study, Felgenhauer and Jarvis<ref name="afjarvis">{{citation|title=Enumerating possible Sudoku grids|first1=Bertram|last1=Felgenhauer|first2=Frazer|last2=Jarvis|date=20 June 2005|url=http://www.afjarvis.org.uk/sudoku/sudoku.pdf}}.</ref><ref name="afj2" /> analyzed the [[permutation]]s of the top band used in valid solutions. Once the Band1 [[symmetry in mathematics|symmetries]] and [[equivalence class]]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.

===={{anchor|Transformations}}Essentially different solutions====

===== The sudoku symmetry group =====

The precise structure of the sudoku symmetry [[Group (mathematics)|group]] can be expressed succinctly using the [[wreath product]] (≀). The possible row (or column) permutations form a group [[Isomorphic group|isomorphic]] to ''S''<sub>3</sub> ≀ ''S''<sub>3</sub> of order 3!<sup>4</sup> = 1,296.<ref name=":3" /> The whole rearrangement group is formed by letting the transposition operation (isomorphic to ''C''<sub>2</sub>) act on two copies of that group, one for the row permutations and one for the column permutations. This is ''S''<sub>3</sub> ≀ ''S''<sub>3</sub> ≀ ''C''<sub>2</sub>, a group of order 1,296<sup>2</sup> × 2 = 3,359,232. Finally, the relabelling operations commute with the rearrangement operations, so the full sudoku (VPT) group is (''S''<sub>3</sub> ≀ ''S''<sub>3</sub> ≀ ''C''<sub>2</sub>) × ''S''<sub>9</sub> 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 (group theory)|orbit]] of grids under the action of the rearrangement [[Group (mathematics)|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 class]]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;<ref name="sudgroup">{{cite web|last=Ed Russell and Frazer Jarvis|date=7 September 2005|title=There are 5472730538 essentially different Sudoku grids... and the Sudoku symmetry group|url=http://www.afjarvis.org.uk/sudoku/sudgroup.html|access-date=20 October 2013|website=Frazer Jarvis's home page|publisher=University of Sheffield}}</ref> 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'''.<ref name="sudgroup" /><ref>{{Cite web|last=Ed Russell, Frazer Jarvis|date=January 25, 2006|title=Mathematics of Sudoku II|url=http://www.afjarvis.org.uk/sudoku/russell_jarvis_spec2.pdf}}</ref>

===== Completeness of the sudoku symmetry group =====

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 <math>n^2 \times n^2</math> grids.<ref>{{cite journal|last1 = Adler|first1 = Aviv|last2 = Adler|first2 = Ilan|date = 2008|title = Fundamental Transformations of Sudoku Grids|url = https://adler.ieor.berkeley.edu/ilans_pubs/suduko_2008.pdf|journal = Mathematical Spectrum|volume = 41|issue = 1|pages = 2–7}}</ref>

==See also==
* [[Combinatorial explosion]] (with summary of grid count of Sudoku compared to Latin squares)
* [[Dancing Links]]
* [[Glossary of Sudoku]]
* [[Sudokian]]
* [[Sudoku code]]

==References==
{{Reflist|30em}}

==Further reading==
*{{cite book|title= Taking Sudoku Seriously: The math behind the world's most popular pencil puzzle|title-link=Taking Sudoku Seriously|first1=Jason|last1=Rosenhouse|author1-link=Jason Rosenhouse|first2=Laura|last2=Taalman|author2-link=Laura Taalman|publisher=Oxford University Press|year=2011}}

==External links==
* [http://plus.maths.org/latestnews/jan-apr06/sudoku/index.html V. Elser's difference-map algorithm also solves Sudoku]
* [http://www.visual-prolog.com/vip/example/pdcExample/sudoku.htm Sudoku Puzzle — an Exercise in Constraint Programming and Visual Prolog 7] by Carsten Kehler Holst (in [[Visual Prolog]])
* [https://www.ams.org/notices/200706/tx070600708p.pdf Sudoku Squares and Chromatic Polynomials] by [[Agnes M. Herzberg|Herzberg]] and Murty, treats Sudoku puzzles as [[graph coloring|vertex coloring]] problems in [[graph theory]].
{{Mathematics of}}

{{DEFAULTSORT:Mathematics of Sudoku}}
[[Category:Sudoku]]
[[Category:Latin squares]]
[[Category:Abstract strategy games]]
[[Category:Recreational mathematics]]