Re: [Caml-list] Sudoku solver

[Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>]

    Bonjour,

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

The constraint "a single digit by block" is named "all different"  in
combinatorial optimization literature. The problem is that your
implementation is too naive : the "optimal" version (in the sense it can
ensure you always make a choice that has at least one solution for the
'alldiff' constraint) needs a matching algorithm and some graph theory.

There is a nice paper by Helmut Simonis "Sudoku as a constraint problem"
with reference to the relevant paper for the algorithms.

    http://www.icparc.ic.ac.uk/~hs/

You could also try to write a solver with FaCiLe (which actually contains
the optimal algorithm for "alldiff" constraints)


        Diego Olivier