Sudoku solver

[Albert van der Horst]

In article <87iodoakft.fsf at elektro.pacujo.net>,
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.

That is a more reasonable time for a realistic algorithm. This puzzle
takes 255 ms in a program that I wrote in 2008 in Forth.

>
>
>Marko

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert at spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst