English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

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:23)
From: Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@e...>
Subject: Re: [Caml-list] Sudoku solver

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


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

        Diego Olivier