Re: [Caml-list] Sudoku solver

[Alain Frisch <Alain.Frisch@inria.fr>]

Jon Harrop wrote:
> I'll add links from my page to everyone else's OCaml Sudoku solvers, if that's 
> ok. :-)

No problem for me.

> I found the 1905-solution "Sky blunder" to be a good example (warning: 6' 
> penis):
> 
>   http://www.sudoku.org.uk/blunder.htm

$ time ./sudoku < sky > /dev/null
14.40s user 0.01s system 98% cpu 14.630 total
$ time ./af-sudoku-brute < sky > /dev/null
0.05s user 0.00s system 74% cpu 0.068 total
$ time ./af-sudoku < sky > /dev/null
0.14s user 0.01s system 87% cpu 0.168 total

>>I guess your choice of a functional data structure explains the 100x
>>slow-down... Hint: copying an array of 81 integers is fast.
> 
> 
> I'd be surprised if the functional data structure was responsible for a 100x 
> slowdown, 10x maybe. I was going to optimise it but, because it solves 
> puzzles in <1sec anyway, I decided to concentrate on making it concise 
> instead.

Using this compare function:

let compare (x1,y1) (x2,y2) = if x1 = x2 then y1 - y2 else x1 - x2

already doubles the speed of your program. In general, the built-in
polymorphic comparisons are a bad idea as soon as effiency matters.

>>Interestingly, disabling these optimizations does not seem to 
>> change the performance significantly.
> On real Sudoku puzzles?

Hard to tell, I'd need to find a slower machine ;-)  For today's puzzle
from http://www.sudoku.org.uk/daily.asp:

$ time ./sudoku < daily > /dev/null
0.25s user 0.00s system 86% cpu 0.291 total
$ time ./af-sudoku < daily > /dev/null
0.00s user 0.00s system 76% cpu 0.001 total
$ time ./af-sudoku-brute < daily > /dev/null
0.00s user 0.00s system 81% cpu 0.001 total


> I found a brute force solver written in Lisp on the net. My implementation was 
> much slower for valid Sudoku puzzles but just as fast for Sky's erroneous one 
> and much faster at finding any solution from a blank board. Of course, I may 
> well have been measuring nothing more than language start-up time...

Again, my solvers give the first solution in 0.00s from a blank board ;-)

I'm not yet convinced that for solving 9x9 grids, complex resolution
techniques from constraint solving bring much. They do probably for
larger grids and maybe for problem generation...

-- Alain