Solves Sudoku.
S = sudoku_solve ( X ) S = sudoku_solve ( X , verbose ) S = sudoku_solve ( X , verbose , params ) S = sudoku_solve ( X , verbose , params , level ) S = sudoku_solve ( X , verbose , params , level , nsmax ) [S,iter,maxlevel] = sudoku_solve ( ... )
a 9-by-9 matrix, with 0 for unknown entries
a boolean. Set to %t to display the state of the matrix. (default = %f)
an array of integers. When the number of unknown cells is strictly lower than p, then the associated algorithm is used. (set to 0 to disable this algorithm) (default = 64, i.e. the algorithm works only when there is less than 64 unknowns)
solve by logic
guessing
integer, the current level of recursive backtracking. (default = 0)
integer. The maximum number of solution to find. Set to %inf to compute all the solutions of the sudoku. (default = 1)
a list of 9-by-9 matrix. The solutions of the sudoku. If S(i) contains zeros, they stand for unsolved entries. S contains at most nsmax elements.
number naked singles steps
number hidden singles steps
number locked candidates steps
number naked pairs steps
number hidden pair steps
number naked triples steps
number hidden triples steps
number naked quad steps
number hidden quad steps
number X-Wing steps
number Bi-Color steps
number X-Cycle steps
number of recursive calls
the maximum level of the call tree in the nested recursive search used in the guess-based strategy
Using logic-based algorithm and Recursive Backtracking (i.e. guessing) when logic failed to solve the puzzle. This uses two algorithms * a logic-based algorithm with naked singles, hidden singles, locked candidates, naked pairs, hidden pairs, naked triples, hidden triples, naked quads, hidden quads, X-Wings, and, if this fails, * a recursive backtracking algorithm designed by Cleve Moler and published in The Mathworks News and Notes, 2009.
On output, the test and(S(:) > 0) returns %t if the puzzle is solved.
When recursive backtracking is necessary, we randomly permute the guesses. This allows to use the algorithm to generate random sudokus because it allows to sample the search space more evenly. In case where the sudoku has multiple solutions, it is likely that the solver might produce different solutions if run several times.
The strategy for chosing the cell which serves to guess is to select the cell which has the least number of candidates. This allows to systematically chose the tree which has the least size, and dramatically increase the speed of the algorithm when several guesses are needed. Indeed, this allows to reduce the probability that each candidates is a wrong guess and increases the probability that, if our guess is wrong, the algorithm will know it as quickly as possible.
The default threshold is set to 81-17 = 64. Indeed, Royle Gordon has found many 17-hints sudoku with unique solutions, but no 16-hint uniquely solvable sudokus. This suggests that if there is less than 17 givens, therefore we have to use guessing and that no logic-based algorithm can find the solution.
Programming Sudoku, Wei-Meng Lee, 2006
Royle Gordon, http://units.maths.uwa.edu.au/~gordon/sudokumin.php