Re: [Caml-list] Sudoku solver

[Jon Harrop <jon@ffconsultancy.com>]

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

> 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