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: 2005-11-15 (09:00) From: Alain Frisch Subject: Re: [Caml-list] Sudoku solver
```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

```