This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Sudoku solver
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Alain Frisch Subject: Re: [Caml-list] Sudoku solver
```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

Using this compare function:

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

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

```