Sudoku solver

[Ian Kelly]

On Wed, Mar 25, 2015 at 2:31 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
> Ian Kelly <ian.g.kelly at gmail.com>:
>
>> The test puzzle that you posted has 23 values already filled in. How
>> does it perform on harder puzzles with only 17 clues (the proven
>> minimum)? One would expect it to be around a million times slower.
>
> Just try it. The example had a minimum of clues (drop one clue and
> you'll get multiple solutions).
>
> <URL: http://www.telegraph.co.uk/news/science/science-news/9359579/W
> orlds-hardest-sudoku-can-you-crack-it.html> mentions this puzzle:
>
> ========================================================================
> 8 . . . . . . . .
> . . 3 6 . . . . .
> . 7 . . 9 . 2 . .
> . 5 . . . 7 . . .
> . . . . 4 5 7 . .
> . . . 1 . . . 3 .
> . . 1 . . . . 6 8
> . . 8 5 . . . 1 .
> . 9 . . . . 4 . .
> ========================================================================
>
> It takes about 2 seconds for my Python program to find the answer but it
> spends a total of 110 seconds to exhaust the problem space.
>
> The analogous C program finished the whole thing in 200 milliseconds.

"Hard" for a human doesn't necessarily mean "hard" for a programmatic
solver in this case. Try your solver on this one:

$ cat sudoku2.dat
. . . 7 . . . . .
1 . . . . . . . .
. . . 4 3 . 2 . .
. . . . . . . . 6
. . . 5 . 9 . . .
. . . . . . 4 1 8
. . . . 8 1 . . .
. . 2 . . . . 5 .
. 4 . . . . 3 . .

I tried the first puzzle you posted, and it took about a second. I
then started running it on this one before I started typing up this
post, and it hasn't finished yet. While that was running, I then tried
running Norvig's solver on this puzzle, and it completed in about 0.07
seconds.

For the curious, this puzzle was arbitrarily collected from
http://theconversation.com/good-at-sudoku-heres-some-youll-never-complete-5234