Sudoku solver

[BartC]

On 26/03/2015 00:07, Ian Kelly wrote:
> On Wed, Mar 25, 2015 at 2:31 PM, Marko Rauhamaa <marko at pacujo.net> wrote:

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

I tried my own brute-force solver, which normally takes 100msec, and it 
took 2 seconds for your hard puzzle, about 20 times longer. (In a 
language using a bytecode interpreter, not Python.)

Using Pypy, it took 90 seconds, instead of 1 second or so. So still 
possibly faster than a human (faster than me certainly).

-- 
Bartc