Version française
Home     About     Download     Resources     Contact us    

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

Browse thread
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 <Alain.Frisch@i...>
Subject: Re: [Caml-list] Sudoku solver
Jon Harrop wrote:
> Here is a little OCaml program to solve Sudoku puzzles:

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

Here it is:

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

$ cat puzzle

$ 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