Solves Sudoku.
Y = sudoku_solvebylogic ( X ) Y = sudoku_solvebylogic ( X , verbose ) [Y,iter,C,L] = sudoku_solvebylogic ( ... )
a 9-by-9 matrix, with 0 for unknown entries
a boolean. Set to %t to display the state of the matrix. (default = %f)
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.
the number of steps required by each algorithm
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-Wings steps
number Bi-Coloring steps
number X-Cycle steps
a cell array of candidate vectors for each cell.
the number of candidates for each cell
%t if a conflict has been detect (i.e. it is guaranteed that the sudoku has no solution), %f if not.
Using logic-based algorithm only. This is a combination of various algorithms : 1 naked singles, 2 hidden singles, 3 locked candidates, 4 naked pairs, 5 hidden pairs. 6 naked triples, 7 hidden triples, 8 naked quads, 9 hidden quads, 10 X-Wings. 11 2-colors 12 X-Cycles
The algorithm uses naked singles as much as it can. If no improvement can be done with naked singles, we search for hidden singles. If hidden singles were able to improve the sudoku, we switch back to naked singles. If no hidden single was able to improve the sudoku, we search for locked candidates. This process is repeated for each searching algorithm, until either the sudoku is solved and we quit, or the sudoku is unsolved, and we quit.
The measure of the progress of each step uses both the number of unknowns and the number of candidates. If the number of unknowns or the number of candidates has decreased, there was an improvement. The fact that the candidates are taked into account for the progress measure allows to solve the most difficult sudokus, where the best that we can expect is that each algorithm only allows to remove some candidates until we finally can identify either a naked single or a hidden single, and thus, confirm a cell.
The iter array allows to measure the difficulty of the puzzle. Largest non-zero entries in the array indicate a larger number of different strategy required. This can be computed with nstrats = sum(iter>0). The number of rounds, i.e. the number of global iterations through the strategies can be deduced with nrounds = sum(iter). A larger number of rounds indicate a larger number of interactions between different strategies.
When an unknown cell with no candidates is detected, there is a conflict and we are sure that the sudoku has no solution. In this case, the algorithms stops and returns. This may save a lot of iterations which could possibly set digits in the sudoku, and would finally fail anyway.
Note on hidden and naked subsets.
Consider a row, column or block with n unfixed entries. Assume that there are p cells with a naked subset with candidates (a1,a2,...,ap). We can prove that there is an hidden subset of length n-p. Indeed, consider the situation of the n-p cells, after the resolution of the naked subset: the candidates (a1,a2,...,ap) have been eliminated. Therefore, before the resolution, there was n-p cells containing n-p candidates plus the additionnal candidates (a1,a2,...,ap). Therefore, this was an hidden subset with n-p cells. For example, if there is a row with 5 unfixed cells, and if there is a hidden quad (4 candidates), there is also a naked single.
The corollary of the previous result is that, if we have procedures to find naked subsets of length 1, 2, 3, 4 and hidden subsets of length 1, 2, 3, 4, it is useless to search for naked or hidden subsets of length 5, 6, 7, 8. Let us prove this. Consider the worst situation of a row, column or block where there are 9 unfixed cells. There are at most 9 candidates in this area. If there is an hidden quintet (5 candidates), there is also a naked quad. If there is an hidden sextet (6 candidates), there is also an naked triple. And so on.
TODO : use Alternating Inference Chain strategies.
Programming Sudoku, Wei-Meng Lee, 2006
Royle Gordon, http://units.maths.uwa.edu.au/~gordon/sudokumin.php