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" externalconstraint 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 andavoiding 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 programwith 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!-)
SudokuPL.hs
Description: Binary data
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
