Sudoku solver

[Marko Rauhamaa]

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.


Marko