So I wanted something to do and wrote a Sudoku solver; I’ve never liked (or even done) Sudoku but ever since Nigel Ross told me of his travails of solving it in Prolog* I’ve wanted to have a go.
So I went for a nice long walk, worked out the algorithm (approximately), worked out the data structures in my head, came home, roughed it out in Python, got it working, and fed a newspaper puzzle into it.
Aaaaaaannnndd… and it never got past the loader. This is because I’d written the damn thing properly:
- start with a blank grid where every cell (range 0..80 inclusive) can contain any possibility in the range 1..9
- load the puzzle by setting specific cells to be specific numbers
- each time you set a cell to value N, elide possibility N from the possibilities of all other companion cells in the relevant row, column, and 3×3 square
- if the elision reduces a companion cell to a single possibility then (v. important) recursively elide that from all of its companion cells
- the grid is now stable but may still contain cells that have multiple possibilities
- iterate through the cells with the fewest remaining possibilities; for each one, clone the grid and use use the clone to test each possibility in turn (by recursing step 3)
- when no cell contains more than one possibility, the puzzle is solved.
…except the newspaper sudokus which I’d decided to use as test vectors never made it past step 5; the puzzles were so data-rich that they were solved by the loading process without even using the clone-and-recurse search mechanism.
Most disappointing. Most disappointed in mankind. I had to delete bits of data from the ‘newspaper-grade’ puzzles to get the engine to start hunting.
The interesting thing is that for an experiment I’ve now added two extra constraints – that numbers on the diagonals be unique – and the result seems to be pathological. The puzzles go from instant solution to indefinitely chugging. Hmmm…
* and of wanting to wire it to an OCR system to save typing-in the puzzles; Nigel is an über-geek