[Haskell-cafe] Code Review: Sudoku solver

[Claus Reinke]

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

as I said, it is reasonable that this covers the first group of constraints
(every position in each coordinate holds a positive single-digit number, 
every positive single-digit number occurs at most once in each coordinate).

what I can't quite seem to be able to make out, though, is how that would
cover the second group of constraints we discussed (every number occurs
at least once in each coordinate), in terms of using it for propagation and
avoiding search: if I have a line in which no position is uniquely determined 
(all positions have a current domain of size>1), but only one of the positions 
(i) has a domain including the number n, then that group of constraints 
allows me to assign n to i, without guessing.

wouldn't the labelling in the FD solver generate all the possible numbers 
in the domain of i, up to n, before committing to n on i as the only option 
that is consistent with the constraints? while equivalent from a declarative
point of view, that would be a lot less efficient, not to mention other
propagation techniques that depend on inspecting and modifying the
current domains of more than one position without actually instantiating
any variables.

btw, I thought it would be easy to augment the declarative spec from 
which all those constraints are generated, to expose this second group 
of constraints, but since the domains are implicit, I don't see how the 
"assign a number to each position" and the "assign a position to each 
number" constraints could communicate about their separate progress
in narrowing the search space (other than when either group uniquely 
determines a number on a position, or by having the prolog code 
inspect the low-level representation of constraints).

if I compare the Prolog version generated by the attached Haskell program
with my current Haskell version, both in code interpreters, then the Haskell 
version is significantly faster. is that only because of details or because of 
more propagation?

cheers,
claus

(*) closed-world or open-world, but small-world for sure!-)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: SudokuPL.hs
Type: application/octet-stream
Size: 1870 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060406/35d4e139/SudokuPL.obj