[Haskell-cafe] Code Review: Sudoku solver

[Tom Schrijvers]

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 
>> rules.
>
> 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 
tricks:
http://www.computational-logic.org/iccl/master/lectures/winter05/fcp/fcp/sudoku.pdf

Cheers,

Tom

--
Tom Schrijvers

Department of Computer Science
K.U. Leuven
Celestijnenlaan 200A
B-3001 Heverlee
Belgium

tel: +32 16 327544
e-mail: tom.schrijvers at cs.kuleuven.be