<< sudoku_solverecursive Solve Utilities >>

Sudoku Toolbox >> Solve > sudoku_solvesa

sudoku_solvesa

Solves Sudoku.

Calling Sequence

Y = sudoku_solvesa ( X )
Y = sudoku_solvesa ( X , timeout )
Y = sudoku_solvesa ( X , timeout , verbose )
[Y,iter] = sudoku_solvesa ( ... )

Parameters

X:

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

timeout:

number of seconds after which we give up (default 60)

verbose:

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

Y:

a 9-by-9 matrix. If Y contains zeros, they stand for unsolved entries. The test and(Y(:) > 0) allows to see if the puzzle is solved.

iter:

the number of iterations required

Description

Uses Simulated Annealing to solve a sudoku. It might happen that, on output, the sudoku is not solved. Because of the randomized behaviour of this algorithm, running the solver again might lead to a sucessful resolution.

In general, this algorithm finds a solution of a given sudoku, but rather slowly. It might be compared to a fast version of filling a sudoku with a pair of dice.

The initial grid is filled with digits so that each block contains exactly one digit 1 to 9. The rows and columns constraints are violated in this initial grid.

The algorithms then uses a neighbourhood function which select a block, select two cells in that block, and switch the values.

The improvement is measured with a cost function, which count the number of times the row and column constraints are violated. This is a very inaccurate measure of the progress of the algorithm. It might lead to sudokus where the cost function value is very low (e.g. 4), but the number of wrong entries is very high (e.g. 44).

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_solvesa(X)
sudoku_solvesa(X,10,%t)

Authors

Bibliography

"Metaheuristics can solve sudoku puzzles", Rhyd Lewis, J Heuristics (2007) 13: 387-401

http://xianblog.wordpress.com/2010/02/23/sudoku-via-simulated-annealing/

http://www.feynmanlectures.info/sudoku/pss.html


<< sudoku_solverecursive Solve Utilities >>