Brute force sudoku cracker
Tom Anderson
twic at urchin.earth.li
Wed Sep 21 14:28:56 EDT 2005
On Wed, 21 Sep 2005 david.blume at gmail.com wrote:
> Excellent strategies are provided by Dan Rice's blog:
> http://sudokublog.typepad.com/sudokublog/2005/08/two_and_three_i.html
There's an interesting remark in this post:
http://sudokublog.typepad.com/sudokublog/2005/08/where_do_sudoko.html
"Some Sudoku generators skip the step of generating a board altogether.
It's enough to place some random numbers in the board and see if it has a
solution. For a backtracking solver, which can solve puzzles very quickly,
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
the time wasted analyzing impossible sets of clues will be minor. For a
human-style solver, it seems reasonable to exclude the possibility of
self-contradictory clues by first generating a consistent underlying
board."
He seems to think that backtrackers are faster than reasoners. That's
somewhat counter-intuitive; i wonder if it's really true. It would
certainly be rather sad if it was.
> You won't find any better solver than this:
> http://sudoku.sourceforge.net/
That's a fairly straightforward backtracker. In fact, it's the solver
which inspired me to write mine - which i believe has a more sophisticated
heuristic (i haven't compared them formally, but my heuristic
sophistication estimation heuristic - which is itself, of course, fairly
sophisticated - suggests that it is). Clearly, what we need is a sudoku
solver shootout.
tom
--
everything from live chats and the Web, to the COOLEST DISGUSTING PORNOGRAPHY AND RADICAL MADNESS!!
More information about the Python-list
mailing list