Op 2005-09-21, Tom Anderson schreef <[EMAIL PROTECTED]>: > On Mon, 19 Sep 2005, Antoon Pardon wrote: > >> Op 2005-09-17, Tom Anderson schreef <[EMAIL PROTECTED]>: >>> 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 -- http://mail.python.org/mailman/listinfo/python-list
