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. tom -- everything from live chats and the Web, to the COOLEST DISGUSTING PORNOGRAPHY AND RADICAL MADNESS!! -- http://mail.python.org/mailman/listinfo/python-list
