Brute force sudoku cracker

[Tom Anderson]

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.

tom

-- 
everything from live chats and the Web, to the COOLEST DISGUSTING 
PORNOGRAPHY AND RADICAL MADNESS!!