Editing Sudoku (section)

== Mathematics of Sudoku ==
[[File:Sudoku Puzzle (an automorphic puzzle with 18 clues).svg|thumb|220px|A Sudoku with 18 clues and two-way diagonal symmetry]]

{{Main|Mathematics of Sudoku}}

This section refers to classic Sudoku, disregarding jigsaw, hyper, and other variants. A completed Sudoku grid is a special type of [[Latin square]] with the additional property of no repeated values in any of the nine blocks (or ''boxes'' of 3×3 cells).<ref>{{cite journal
 | last = Keedwell | first = A. D.
 | date = November 2006
 | doi = 10.1017/s0025557200180234
 | issue = 519
 | journal = [[The Mathematical Gazette]]
 | jstor = 40378190
 | pages = 425–430
 | title = Two remarks about Sudoku squares
 | volume = 90}}</ref>

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
 | issue = 5
 | journal = IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
 | pages = 1052–1060
 | title = Complexity and completeness of finding another solution and its application to puzzles
 | archive-url = https://web.archive.org/web/20200303233817/http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf
 | archive-date = 2020-03-03
 | url = http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf
 | volume = E86-A
 | year = 2003}}</ref> Many [[Sudoku solving algorithms]], such as [[Brute-force search|brute force]]-backtracking and [[dancing links]] can solve most 9×9 puzzles efficiently, but [[combinatorial explosion]] occurs as ''n'' increases, creating practical limits to the properties of Sudokus that can be constructed, analyzed, and solved as ''n'' increases. A Sudoku puzzle can be expressed as a [[graph coloring]] problem.<ref name="Lewis2015">{{cite book |last=Lewis |first=R. |title=A Guide to Graph Colouring: Algorithms and Applications |publisher=Springer |year=2015 |isbn=978-3-319-25728-0 |doi=10.1007/978-3-319-25730-3 |s2cid=26468973 |oclc=990730995 }}</ref> The aim is to construct a 9-coloring of a particular graph, given a partial 9-coloring.

The fewest clues possible for a proper Sudoku is 17.<ref>{{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> Tens of thousands of distinct Sudoku puzzles have only 17 clues.<ref name=seventeen3>{{cite web |url=http://www.csse.uwa.edu.au/~gordon/sudokumin.php |title=Minimum Sudoku |access-date=February 28, 2012 |last=Royle |first=Gordon | author-link = Gordon Royle |archive-date=November 26, 2006 |archive-url=https://web.archive.org/web/20061126162713/http://www.csse.uwa.edu.au/~gordon/sudokumin.php |url-status=dead }}</ref>

The number of classic 9×9 Sudoku solution grids is 6,670,903,752,021,072,936,960, or around {{val|6.67|e=21}}.<ref>{{cite OEIS|A107739|Number of (completed) sudokus (or Sudokus) of size n^2 X n^2}}</ref> The number of essentially different solutions, when [[symmetries]] such as rotation, reflection, permutation, and relabelling are taken into account, is much smaller, 5,472,730,538.<ref>{{cite OEIS|A109741|Number of inequivalent (completed) n^2 X n^2 sudokus (or Sudokus)}}</ref>

Unlike the number of complete Sudoku grids, the number of minimal 9×9 Sudoku puzzles is not precisely known. (A minimal puzzle is one in which no clue can be deleted without losing the uniqueness of the solution.) However, statistical techniques combined with a puzzle generator show that about (with 0.065% relative error) 3.10&nbsp;×&nbsp;10<sup>37</sup> minimal puzzles and 2.55&nbsp;×&nbsp;10<sup>25</sup> nonessentially equivalent minimal puzzles exist.<ref name="UnbiasedStat">{{cite book | first = Denis | last = Berthier | chapter-url = http://hal.archives-ouvertes.fr/hal-00641955 |date=December 4, 2009 |title=Innovations in Computing Sciences and Software Engineering |editor= Elleithy, Khaled |pages=165–70 |chapter=Unbiased Statistics of a CSP – A Controlled-Bias Generator | doi = 10.1007/978-90-481-9112-3 | bibcode = 2010iics.book.....S | isbn = 978-90-481-9111-6 |publisher=Springer |access-date = December 4, 2009 }}</ref>