[Haskell-cafe] Code Review: Sudoku solver
Tom.Schrijvers at cs.kuleuven.ac.be
Thu Apr 6 14:49:42 EDT 2006
On Thu, 6 Apr 2006, Claus Reinke wrote:
>> Curry does not have a constraint solver of its own. It simply delegates all
>> constraints to the FD solver of SICStus Prolog.
> or that of SWI Prolog (which prompted my attempt to install Curry).
> which was implemented by.. hi, again!-) (*)
The SWI-Prolog FD library is just a prototype implementation... looking
for someone to replace it with a state-of-the-art implementation.
>> The all_different constraint subsumes the rules that you describe,
>> depending on the consistency algorithm used. FD solvers implement general
>> but efficient algorithms that are much more complex than a few simple
> I haven't yet been able to get Curry to work on my windows machine,
> but it seems to do a straightforward translation of these constraints to
> Prolog > +FD solver, close to the one I've attached (an easy way to "use" external
> constraint solvers from Haskell;-).
> the docs you pointed to state that all_different, in declarative view, simply
> translates into mutual inequalities between the list members, and although I
> don't fully understand the sources, they seem to confirm that not much more
> is going on.
The SWI-Prolog prototype library does nothing more than the declarative
meaning, that's why it's a prototype.
State-of-the-art all_different implementations are a lot more complicated
(often based on graph algorithms) to do very strong propagation.
Here is a paper about solving Sudoku with constraint (logic )
programming comparing a number of all_different algorithms and additional
Department of Computer Science
tel: +32 16 327544
e-mail: tom.schrijvers at cs.kuleuven.be
More information about the Haskell-Cafe