Sudoku solver

[Ed W]

OK, so I must be the last person left who hasn't written a Sudoku solver...

The "Norvig solver" is one of the most emulated algorithms for solving
sudoku, and it basically boils down to a depth first algorithm which
simultaneously modifies the board state, whilst it searches the board.
Arguably a more functional approach is to separate the analysis of the
board to determine how what changes can be made, from the action of
updating the board.

This solver applies the later approach and additionally tries to use
heuristics to find ways to update the board, and only guesses when no
other option is available. I feel it's a much neater algorithm than the
"Norvig" algorithm, and it dodges the challenge of (neatly) aborting a
depth search from deep in the fingers of the search tree.

The heuristics applied are inspired by the rather interesting
mathematical analysis here:
https://www.stolaf.edu/people/hansonr/sudoku/12rules.htm - there is only
one other heuristic which would be interesting to add and that is the
XY-chains (or Y-wing). In my opinion all other chain/colouring analysis
that humans commonly quote is effectively "guessing", but with immediate
backtracking, given that this is computer solver this doesn't appear to
buy us anything (and is computationally expensive)

Performance is moderate, it solves around 80 puzzles a second on a
Macbook Pro (using a single core). However, it's worst case is very
similar to it's average case (unlike the Norvig solver that has some
extreme tails), it's believed that the reduction in branching (ie
heuristics) is responsible for this. Optimisation suggestions appreciated

https://www.stolaf.edu/people/hansonr/sudoku/12rules.htm


Anyway, you can now trivially chalk up another solution on project Euler...

Have fun

Ed W

[Ed W]

Apologies, duff link and failure to [ANN] the subject, corrected

> https://github.com/ewildgoose/elixir-sudoku