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