Brute force sudoku cracker

[Antoon Pardon]

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:
>
> 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