<< Solve Solve sudoku_solveai >>

Sudoku Toolbox >> Solve > sudoku_solve

sudoku_solve

Solves Sudoku.

Calling Sequence

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 ( ... )

Parameters

X:

a 9-by-9 matrix, with 0 for unknown entries

verbose:

a boolean. Set to %t to display the state of the matrix. (default = %f)

params:

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)

params(1):

solve by logic

params(2):

guessing

level :

integer, the current level of recursive backtracking. (default = 0)

nsmax :

integer. The maximum number of solution to find. Set to %inf to compute all the solutions of the sudoku. (default = 1)

S:

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.

iter(1):

number naked singles steps

iter(2):

number hidden singles steps

iter(3):

number locked candidates steps

iter(4):

number naked pairs steps

iter(5):

number hidden pair steps

iter(6):

number naked triples steps

iter(7):

number hidden triples steps

iter(8):

number naked quad steps

iter(9):

number hidden quad steps

iter(10):

number X-Wing steps

iter(11):

number Bi-Color steps

iter(12):

number X-Cycle steps

iter(13):

number of recursive calls

maxlevel:

the maximum level of the call tree in the nested recursive search used in the guess-based strategy

Description

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.

Examples

X = [
0 0 0   0 0 0   0 0 0
0 0 0   0 0 0   5 3 0
9 0 0   0 3 7   0 0 0
0 0 2   3 0 1   0 9 6
0 4 7   6 9 0   1 8 0
0 0 6   7 8 5   0 0 0
0 5 0   0 2 0   9 0 3
0 3 0   9 0 0   6 0 8
8 0 0   0 1 0   4 7 0
]
sudoku_solve(X)
sudoku_solve(X,%t)
sudoku_solve(X,%t,[64 %inf]) // Default settings
sudoku_solve(X,%t,[0 %inf]) // For easy cases (it is generally faster to use just guessing)

X = [
0 0 0   0 0 0   0 0 0
9 0 0   0 0 4   0 3 6
0 0 0   0 7 2   0 0 9
3 0 0   0 0 0   0 0 5
0 1 4   0 0 0   8 0 0
0 2 5   0 1 0   0 0 0
0 0 6   1 0 0   0 0 3
0 0 0   0 0 6   0 4 0
0 0 2   4 8 9   0 0 0
]
sudoku_solve(X)

X = [
1 2 0    0 3 0    0 4 0
6 0 0    0 0 0    0 0 3
3 0 4    0 0 0    5 0 0
2 0 0    8 0 6    0 0 0
8 0 0    0 1 0    0 0 6
0 0 0    7 0 5    0 0 0
0 0 7    0 0 0    6 0 0
4 0 0    0 0 0    0 0 8
0 3 0    0 4 0    0 2 0
]
sudoku_solve(X)

X = [
0 2 0   0 3 0   0 4 0
6 0 0   0 0 0   0 0 3
0 0 4   0 0 0   5 0 0
0 0 0   8 0 6   0 0 0
8 0 0   0 1 0   0 0 6
0 0 0   7 0 5   0 0 0
0 0 7   0 0 0   6 0 0
4 0 0   0 0 0   0 0 8
0 3 0   0 4 0   0 2 0
]
sudoku_solve(X)

Authors

Bibliography

Programming Sudoku, Wei-Meng Lee, 2006

Royle Gordon, http://units.maths.uwa.edu.au/~gordon/sudokumin.php

<< Solve Solve sudoku_solveai >>