Brute force sudoku cracker

[Antoon Pardon]

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.

 

[Dennis Lee Bieber]

Op 2005-09-21, Tom Anderson schreef <[email protected]>:

Well I stand corrected. Thanks for the information.

I wouldn't be too sure... I have a book of the deadly puzzles... The
last third is full of puzzles that come up with multiple candidate
paths, that have sometimes required me to backtrack parts at least twice
(I typically give up when I get these cycles with split points -- since
I do the puzzles in fountain pen).
--