View source for Sudoku solving algorithms

{{short description|Algorithms to complete a sudoku}}
[[File:Sudoku Puzzle by L2G-20050714 standardized layout.svg|thumb|upright=1.2|right|alt=A typical Sudoku puzzle, a 9x9 grid with several numbers missing|A typical Sudoku puzzle]]
A standard [[Sudoku]] contains 81 cells, in a 9×9 grid, and has 9 boxes, each box being the intersection of the first, middle, or last 3 rows, and the first, middle, or last 3 columns. Each cell may contain a number from one to nine, and each number can only occur once in each row, column, and box. A Sudoku starts with some cells containing numbers (''clues''), and the goal is to solve the remaining cells. Proper Sudokus have one solution.<ref>{{Cite web
| author       = Mahmood, Yasser
| title        = More about Sudoku
| url          = https://pi.math.cornell.edu/~mec/Summer2009/Mahmood/More.html#:~:text=A%20well%2Dformed%20Sudoku%20puzzle,that%20has%20a%20unique%20solution.
| website      = Cornell University
| date         = 2009
| access-date  = 2024-11-26
}}</ref> Players and investigators use a wide range of computer algorithms to solve Sudokus, study their properties, and make new puzzles, including Sudokus with interesting symmetries and other properties.

There are several computer algorithms that will solve 9×9 puzzles ({{mvar|n}} = 9) in fractions of a second, but [[combinatorial explosion]] occurs as {{mvar|n}} increases, creating limits to the properties of Sudokus that can be constructed, analyzed, and solved as {{mvar|n}} increases.

==Techniques==

==={{anchor|Sudoku brute force}}Backtracking===
<!-- A link in "Brute-force search" links here -->
[[File:Sudoku solved by bactracking.gif|thumb|upright=1.2|A Sudoku (top) being solved by '''backtracking'''. Each cell is tested for a valid number, moving "back" when there is a violation, and moving forward again until the puzzle is solved.]]
[[File:Sudoku puzzle hard for brute force.svg|thumb|upright=1.2|right|A Sudoku designed to work against the brute force algorithm<ref name="difficult 17 clue">[https://www.flickr.com/photos/npcomplete/2361922699 "Star Burst - Polar Graph"] A polar chart showing a solution path for a Sudoku (Star Burst) using an exhaustive search routine and comment about 17-clue Sudoku.</ref>]]
{{main article|Brute-force search}}
Some hobbyists have developed computer programs that will solve Sudoku puzzles using a [[backtracking]] algorithm, which is a type of [[brute force search]].<ref>[http://intelligence.worldofcomputing.net/ai-search/brute-force-search.html#.WPWK6oWcEiQ http://intelligence.worldofcomputing/brute-force-search] Brute Force Search, December 14th, 2009.</ref> Backtracking is a ''[[depth-first search]]'' (in contrast to a ''[[breadth-first search]]''), because it will completely explore one branch to a possible solution before moving to another branch. Although it has been established that approximately 5.96 x 10<sup>26</sup> final grids exist, a brute force algorithm can be a practical method to solve Sudoku puzzles.

A brute force algorithm visits the empty cells in some order, filling in digits sequentially, or backtracking when the number is found to be not valid.<ref>
{{cite web
 |title       = Backtracking - Set 7 (Sudoku)
 |url         = http://www.geeksforgeeks.org/backtracking-set-7-suduku/
 |website     = GeeksforGeeks
 |access-date  = 24 December 2016
 |archive-url  = https://web.archive.org/web/20160828164622/http://www.geeksforgeeks.org/backtracking-set-7-suduku/
 |archive-date = 2016-08-28
 |language    = English
 }}</ref><ref name="norvig2016">
{{cite web
|last1=Norvig
|first1=Peter
|title=Solving Every Sudoku Puzzle
|url=http://www.norvig.com/sudoku.html
|website=Peter Norvig (personal website)
|access-date=24 December 2016
|language=English
}}</ref><ref>[https://www.flickr.com/photos/npcomplete/2341937186 "Chart of Cells Visited for Solution"] A chart showing a solution path to a difficult Sudoku.</ref><ref name=Zelenski>{{cite AV media | people=Zelenski, Julie | date=July 16, 2008 | title=Lecture 11 &#124; Programming Abstractions (Stanford) | publisher=Stanford Computer Science Department | url = https://www.youtube.com/watch?v=p-gpaIGRCQI}}</ref> Briefly, a program would solve a puzzle by placing the digit "1" in the first cell and checking if it is allowed to be there. If there are no violations (checking row, column, and box constraints) then the algorithm advances to the next cell and places a "1" in that cell. When checking for violations, if it is discovered that the "1" is not allowed, the value is advanced to "2". If a cell is discovered where none of the 9 digits is allowed, then the algorithm leaves that cell blank and moves back to the previous cell. The value in that cell is then incremented by one. This is repeated until the allowed value in the last (81st) cell is discovered.

The animation shows how a Sudoku is solved with this method. The puzzle's clues (red numbers) remain fixed while the algorithm tests each unsolved cell with a possible solution. Notice that the algorithm may discard all the previously tested values if it finds the existing set does not fulfill the constraints of the Sudoku.

Advantages of this method are:
* A solution is guaranteed (as long as the puzzle is valid).
* Solving time is mostly unrelated to [[degree of difficulty]].{{dubious|date=June 2023}}
* The algorithm (and therefore the program code) is simpler than other algorithms, especially compared to strong algorithms that ensure a solution to the most difficult puzzles.

The disadvantage of this method is that the solving time may be slow compared to algorithms modeled after deductive methods. One programmer reported that such an algorithm may typically require as few as 15,000 cycles, or as many as 900,000 cycles to solve a Sudoku, each cycle being the change in position of a "pointer" as it moves through the cells of a Sudoku.<ref>[https://www.flickr.com/photos/npcomplete/2384354604 "Star Burst Leo - Polar Graph"] A polar chart showing a solution path for a Sudoku (Star Burst Leo) using an exhaustive search routine.</ref><ref>[https://www.flickr.com/photos/npcomplete/2341937186 "Chart of Cells Visited for Solution"] A chart showing a solution path for a difficult Sudoku using an exhaustive search routine.</ref>

A different approach which also uses backtracking, draws from the fact that in the solution to a standard sudoku the distribution for every individual symbol (value) must be one of only 46656 patterns.
In manual sudoku solving this technique is referred to as pattern overlay or using templates and is confined to filling in the last values only.
A library with all the possible patterns may get loaded or created at program start. Then every given symbol gets assigned a filtered set with those patterns, which are in accordance with the given clues.
In the last step, the actual backtracking part, patterns from these sets are tried to be combined or overlayed in a non-conflicting way until the one permissible combination is hit upon.
The Implementation is exceptionally easy when using bit vectors, because for all the tests only bit-wise logical operations are needed, instead of any nested iterations across rows and columns.
Significant optimization can be achieved by reducing the sets of patterns even further during filtering. By testing every questionable pattern against all the reduced sets that were already accepted for the other symbols the total number of patterns left for backtracking is greatly diminished.

And as with all sudoku brute-force techniques, run time can be vastly reduced by first applying some of the most simple solving practices which may fill in some 'easy' values.

A Sudoku can be constructed to work against backtracking. Assuming the solver works from top to bottom (as in the animation), a puzzle with few clues (17), no clues in the top row, and has a solution "987654321" for the first row, would work in opposition to the algorithm. Thus the program would spend significant time "counting" upward before it arrives at the grid which satisfies the puzzle. In one case, a programmer found a brute force program required six hours to arrive at the solution for such a Sudoku (albeit using a 2008-era computer). Such a Sudoku can be solved nowadays in less than 1 second using an exhaustive search routine and faster processors.<ref>{{Cite journal
 | last1 = McGuire
 | first1 = Gary
 | last2 = Tugemann
 | first2 = Bastian
 | last3 = Civario
 | first3 = Gilles
 | title = A Game of Sudoku
 | journal = ResearchGate
 | date = 2012
 | url = https://www.researchgate.net/publication/51978217_There_Is_No_16-Clue_Sudoku_Solving_the_Sudoku_Minimum_Number_of_Clues_Problem_via_Hitting_Set_Enumeration/link/64e68f7b0453074fbda95dbe/download?_tp=eyJjb250ZXh0Ijp7ImZpcnN0UGFnZSI6InB1YmxpY2F0aW9uIiwicGFnZSI6InB1YmxpY2F0aW9uIn19
 | format = PDF
 | page = 25
 | access-date = 2024-11-27
}}</ref><sup>p:25</sup>

===Stochastic search / optimization methods===
Sudoku can be solved using stochastic (random-based) algorithms.<ref name="Lewis, R (2007) pp 387-401">Lewis, R (2007) ''Metaheuristics Can Solve Sudoku Puzzles'' Journal of Heuristics, vol. 13 (4), pp 387-401.</ref><ref name="Perez, Meir and Marwala, Tshilidzi (2008)">Perez, Meir and Marwala, Tshilidzi (2008) ''Stochastic Optimization Approaches for Solving Sudoku'' arXiv:0805.0697.</ref> An example of this method is to:
# Randomly assign numbers to the blank cells in the grid.
# Calculate the number of errors.
# "Shuffle" the inserted numbers until the number of mistakes is reduced to zero.
A solution to the puzzle is then found. Approaches for shuffling the numbers include [[simulated annealing]], [[genetic algorithm]] and [[tabu search]]. Stochastic-based algorithms are known to be fast, though perhaps not as fast as deductive techniques. Unlike the latter however, optimisation algorithms do not necessarily require problems to be logic-solvable, giving them the potential to solve a wider range of problems. Algorithms designed for graph colouring are also known to perform well with Sudokus.<ref name="Lewis2015">Lewis, R. ''A Guide to Graph Colouring: Algorithms and Applications''. Springer International Publishers, 2015.</ref> It is also possible to express a Sudoku as an [[integer linear programming]] problem. Such approaches get close to a solution quickly, and can then use branching towards the end. The [[simplex algorithm]] is able to solve proper Sudokus, indicating if the Sudoku is not valid (no solution). If there is more than one solution (non-proper Sudokus) the simplex algorithm will generally yield a solution with fractional amounts of more than one digit in some squares. However, for proper Sudokus, linear programming presolve techniques alone will deduce the solution without any need for simplex iterations. The logical rules used by presolve techniques for the reduction of LP problems include the set of logical rules used by humans to solve Sudokus.

=== Constraint programming ===
A Sudoku may also be modelled as a [[constraint satisfaction problem]]. In his paper ''Sudoku as a Constraint Problem'',<ref>{{cite CiteSeerX|last1=Simonis|first1=Helmut|title=Sudoku as a Constraint Problem |language=en |date=2005|quote=paper presented at the Eleventh International Conference on Principles and Practice of Constraint Programming|citeseerx=10.1.1.88.2964}}</ref> Helmut Simonis describes many ''reasoning algorithms'' based on constraints which can be applied to model and solve problems. Some constraint solvers include a method to model and solve Sudokus, and a program may require fewer than 100 lines of code to solve a simple Sudoku.<ref>{{cite web|author1=Multiple Authors|title=Java Constraint Programming solver|url=http://jacop.osolpro.com|website=JaCoP|publisher=Krzysztof Kuchcinski & Radoslaw Szymanek|access-date=8 December 2016|language=English|format=Java}}</ref><ref>{{cite web|author1=Rhollor|title=Sudokusolver|url=https://github.com/Rhollor/SudoKuSolver|website=GitHub|publisher=Rhollor|access-date=8 December 2016|language=English|format=C++}}</ref> If the code employs a strong reasoning algorithm, incorporating backtracking is only needed for the most difficult Sudokus. An algorithm combining a constraint-model-based algorithm with backtracking would have the advantage of fast solving time – of the order of a few milliseconds<ref>{{Cite web|title=Sudoku - Rosetta Code|url=https://rosettacode.org/wiki/Sudoku#Constraint_Satisfaction_.28Norvig.29|access-date=2021-11-30|website=rosettacode.org}}</ref> – and the ability to solve all sudokus.<ref name="norvig2016" />

===Exact cover===
{{main article|Exact cover#Sudoku}}
Sudoku puzzles may be described as an [[exact cover]] problem, or more precisely, an exact [[hitting set]] problem. This allows for an elegant description of the problem and an efficient solution. Modelling Sudoku as an exact cover problem and using an algorithm such as [[Knuth's Algorithm X]] and his [[Dancing Links]] technique "is the method of choice for rapid finding [measured in microseconds] of all possible solutions to Sudoku puzzles."<ref>
{{cite web |last1=Hanson |first1=Robert M. |date=16 August 2022 |title=Exact Cover Matrix |url=https://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm |language=English}} 
</ref>
An alternative approach is the use of Gauss elimination in combination with column and row striking.

===Relations and residuals===
Let ''Q'' be the 9x9 Sudoku matrix, ''N'' = {1, 2, 3, 4, 5, 6, 7, 8, 9}, and ''X'' represent a generic row, column, or block. ''N'' supplies symbols for filling ''Q'' as well as the [[index set]] for the 9 elements of any ''X''. The given elements ''q'' in ''Q'' represent a [[univalent relation]] from ''Q'' to ''N''. The solution ''R'' is a ''total relation'' and hence a [[function (mathematics)|function]]. Sudoku rules require that the [[restriction (mathematics)|restriction]] of ''R'' to ''X'' is a [[bijection]], so any partial solution ''C'', restricted to an ''X'', is a [[partial permutation]] of ''N''.

Let ''T'' = { ''X'' : ''X'' is a row, column, or block of ''Q'' }, so ''T'' has 27 elements. An ''arrangement'' is either a partial permutation or a [[permutation]] on ''N''. Let ''Z'' be the set of all arrangements on ''N''. A partial solution ''C'' can be reformulated to include the rules as a [[composition of relations]] ''A'' (one-to-three) and ''B'' requiring compatible arrangements:
:<math>Q \xrightarrow{A} T \xrightarrow{B} Z \quad \text{with}\quad A;B \subseteq C .</math>
Solution of the puzzle, suggestions for new ''q'' to enter ''Q'', come from prohibited arrangements <math>\bar{C},</math>, the [[set complement|complement]] of ''C'' in ''Q''x''Z'': useful tools in the calculus of relations are [[Composition of relations#Quotients|residuals]]:
:<math>A \backslash C = \overline{A^T;\bar{C}}</math> maps ''T'' to ''Z'', and
:<math> C/B = \overline{\bar{C};B^T}</math> maps ''Q'' to ''T''.

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

== References ==
{{Reflist|2}}

== External links ==
* http://diuf.unifr.ch/pai/people/juillera/Sudoku/Sudoku.html ''Sudoku Explainer by Nicolas Juillerat''  (Popular for rating Sudokus in general) {{Archive url|url=https://web.archive.org/web/20131112230157/http://diuf.unifr.ch/pai/people/juillera/Sudoku/Sudoku.html|date=2013-11-12}}
* [http://www.ams.org/notices/200904/rtx090400460p.pdf A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles]

[[Category:Sudoku]]
[[Category:Abstract strategy games]]
[[Category:Search algorithms]]