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: Jon Harrop Subject: Re: [Caml-list] Sudoku solver
```On Tuesday 15 November 2005 08:55, Alain Frisch wrote:
> Funny. My father told me about the game last sunday and I was willing to
> write a solver too :-)

On Tuesday 15 November 2005 20:56, Karl Zilles wrote:
> Heh.  My parents showed me a Sudoku puzzle when I last visited them.  I
> solved one just to get a feel for them, then wrote a simple
> constraint/brute force solver in OCaml for fun.  Looks like a lot of us
> have.

LOL. It seems that everyone on the caml-list just discovered and solved
them. :-)

> Here it is:
> http://www.eleves.ens.fr/home/frisch/info/af-sudoku-brute.ml
> http://www.eleves.ens.fr/home/frisch/info/af-sudoku.ml

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

> It is faster than yours.

:-p

> E.g., when displaying all the solutions (there are 247 solutions for the
> example):

I found the 1905-solution "Sky blunder" to be a good example (warning: 6'
penis):

http://www.sudoku.org.uk/blunder.htm

> 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

> The -brute version is a simple-minded brute force search. There other
> one tries to use the constraint "each digit must appear in each bloc"
> (where a bloc is a line, a column, or a 3x3 sub-bloc) to place digits.
> It also chooses a cell with a minimal number of remaining choices when
> branching.

My program uses bitfields to keep track of which digits are valid. That may
make it asymptotically faster than a brute force approach. I haven't thought
about it much though (obviously not as much as Pascal!).

> Interestingly, disabling these optimizations does not seem to
> change the performance significantly.

On real Sudoku puzzles?

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

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

```