Re: [Caml-list] Sudoku solver

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

Jon Harrop wrote:
> Here is a little OCaml program to solve Sudoku puzzles:
> 
>   http://www.ffconsultancy.com/free/sudoku/
> 

Funny. My father told me about the game last sunday and I was willing to
write a solver too :-)

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

It is faster than yours. E.g., when displaying all the solutions (there
are 247 solutions for the example):

$ cat puzzle
001005300050490000
000102064
000000750
600000001
035000000
060903000
000020090
003600100

$ time ./sudoku < puzzle > /dev/null
4.89s user 0.00s system 98% cpu 4.944 total

$ time ./af-sudoku-brute < puzzle > /dev/null
0.02s user 0.00s system 30% cpu 0.068 total

$ time ./af-sudoku < puzzle > /dev/null
0.03s user 0.00s system 37% cpu 0.074 total

(all of them are compiled with ocamlopt without any special option)

I guess your choice of a functional data structure explains the 100x
slow-down... Hint: copying an array of 81 integers is fast.


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. Interestingly, disabling these optimizations does not seem to
change the performance significantly.


-- Alain