[Haskell-cafe] Code Review: Sudoku solver
Claus Reinke
claus.reinke at talk21.com
Thu Apr 6 14:12:36 EDT 2006
> 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
More information about the Haskell-Cafe
mailing list