Re:Show HN: Solving Sudoku using PHP.
by glenjamin on Sunday March 27, 2011 @09:37AM
(#2374943)
The bit you're missing is not the propagation, it's the memoisation. Roughly summarised, norvig's alrogithm is:
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.
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.