Brute force sudoku cracker
in [Python]
|
Prev: Python 2.4 decompiler
Next: triangulation
From: david.blume on 21 Sep 2005 13:35 Bas, you and I are both a little late to the sudoku python experience. Here's my feeble attempt: http://home.earthlink.net/~daliblume/Download/sudoku/index.html Inspired by this article: http://somethinkodd.com/oddthinking/?p=21 Excellent strategies are provided by Dan Rice's blog: http://sudokublog.typepad.com/sudokublog/2005/08/two_and_three_i.html You won't find any better solver than this: http://sudoku.sourceforge.net/
From: Tom Anderson on 21 Sep 2005 14:28 On Wed, 21 Sep 2005 david.blume(a)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!!
From: Tom Anderson on 21 Sep 2005 14:42 On Mon, 19 Sep 2005, Antoon Pardon wrote: > Op 2005-09-17, Tom Anderson schreef <twic(a)urchin.earth.li>: >> On Fri, 16 Sep 2005, Bas wrote: >> >>> -any ideas how to easily incorporate advanced solving strategies? >>> solve(problem1) and solve(problem2) give solutions, but >>> solve(problem3) gets stuck... >> >> the only way to solve arbitrary sudoku problems is to guess. > > That is strange, in al the puzzles that I have solved untill now, I > never needed to guess, unless the puzzle had multiple solutions, which > personnally I find inferior. Well, if we are to believe Lance Fortnow, a fairly expert comptational complexionist, that's probably not generally true: http://weblog.fortnow.com/2005/08/sudoku-revisited.html It's this bit: "Since we don't believe that NP has fast probabilistic algorithms, we expect that there are no efficient procedures to completing a generalized Sudoku grid" That makes me think that there probably isn't a non-backtracking method, since that would almost certainly be polynomial-time. The thing is, the puzzles you encounter in the wild have been designed to be solved by humans, using non-backtracking methods; they're much easier to solve than the general class of Sudoku. tom -- everything from live chats and the Web, to the COOLEST DISGUSTING PORNOGRAPHY AND RADICAL MADNESS!!
From: Antoon Pardon on 22 Sep 2005 08:57
Op 2005-09-21, Tom Anderson schreef <twic(a)urchin.earth.li>: > On Mon, 19 Sep 2005, Antoon Pardon wrote: > >> Op 2005-09-17, Tom Anderson schreef <twic(a)urchin.earth.li>: >>> On Fri, 16 Sep 2005, Bas wrote: >>> >>>> -any ideas how to easily incorporate advanced solving strategies? >>>> solve(problem1) and solve(problem2) give solutions, but >>>> solve(problem3) gets stuck... >>> >>> the only way to solve arbitrary sudoku problems is to guess. >> >> That is strange, in al the puzzles that I have solved untill now, I >> never needed to guess, unless the puzzle had multiple solutions, which >> personnally I find inferior. > > Well, if we are to believe Lance Fortnow, a fairly expert comptational > complexionist, that's probably not generally true: > > http://weblog.fortnow.com/2005/08/sudoku-revisited.html > > It's this bit: > > "Since we don't believe that NP has fast probabilistic algorithms, we > expect that there are no efficient procedures to completing a generalized > Sudoku grid" > > That makes me think that there probably isn't a non-backtracking method, > since that would almost certainly be polynomial-time. > > The thing is, the puzzles you encounter in the wild have been designed to > be solved by humans, using non-backtracking methods; they're much easier > to solve than the general class of Sudoku. Well I stand corrected. Thanks for the information. -- Antoon Pardon |