Home Original page

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