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

> The "optimal algorithm" is not enough; some grids require more (for
> example a "shaving" technique as described by Helmut).

What I understood in Helmut's paper is that most of the Sudoku instances
were backtrack-free when a combination of matching constraints was used
(same with card, cardinality matrix, etc.)

When shaving is allowed, forward checking or just bound consistency closes
almost all the instances without backtracking. That might be a better
advice for "ad hoc" solvers like Frisch's since he seems to be already
doing forward checking.

> where search is not included. So it does not solve all the instances:

It shouldn't be difficult to add a simple search (generate) is it ?

        Diego Olivier