If any of the possible values of a cell is not possible in any of the other conflicting cell than its safe to assume that, that value is the value of this cell.
hope its not confused. check the line 313 to 386 of my code.
1. Construct a 9x9 Array of possibility arrays containing the numbers 1-9.
2. When a possibility array is reduced to 1 element, remove this number from all related arrays (row, column, box).
3. Reduce the arrays to 1 number as specified by the initial puzzle.
4. If, after propagation all possibility arrays have 1 item, the puzzle is solved
5. Otherwise,choose one of the shortest possiblity arrays and try a value, backtrack if this leads to an unsolvable puzzle
The key points are the memoisation of possiblities, and choosing cells with the smallest number of possibilities for the search.
:- use module(library(clpfd)).
Vs ins 1 .. 9,
rows(Rs) :- maplist(all distinct,Rs).
columns(Rs) :- columns(9,Rs).
N > 0,
N1 is N-1,
I put the results on github a while back:
IMHO the fact that it's fast and not very complex to brute-force Sudoku makes it a lot less interesting as a puzzle for people to solve.
A legal puzzle must have only one valid solution.
Update: I googled for a hard sudoku board, got http://www.forbeginners.info/sudoku-puzzles/hard-1.htm It was brute-forced in 0.038 seconds on my laptop. Code is here: