Apologies, duff link and failure to [ANN] the subject, corrected
On 06/07/2016 16:44, Ed W wrote:
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://github.com/ewildgoose/elixir-sudoku
Anyway, you can now trivially chalk up another solution on project
Euler...
Have fun
Ed W
--
You received this message because you are subscribed to the Google Groups
"elixir-lang-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/elixir-lang-talk/5f24a7c7-f011-d8d5-5434-be907eb759b7%40wildgooses.com.
For more options, visit https://groups.google.com/d/optout.
