Brute force sudoku cracker

Antoon Pardon apardon at
Thu Sep 22 14:57:58 CEST 2005

Op 2005-09-21, Tom Anderson schreef <twic at>:
> On Mon, 19 Sep 2005, Antoon Pardon wrote:
>> Op 2005-09-17, Tom Anderson schreef <twic at>:
>>> 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.

Antoon Pardon

More information about the Python-list mailing list