Brute force sudoku cracker
apardon at forel.vub.ac.be
Thu Sep 22 14:57:58 CEST 2005
Op 2005-09-21, Tom Anderson schreef <twic at urchin.earth.li>:
> On Mon, 19 Sep 2005, Antoon Pardon wrote:
>> Op 2005-09-17, Tom Anderson schreef <twic at 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:
> 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.
More information about the Python-list