Chris Rathman wrote:
I've been trying to work through the Palindrome example that is given in
chapter 9 using relational programming and chapter 12 using constraint
programming. Took me a bit to figure out the obvious that the one in
chapter 9 is 4 digit palindromes, and the one in chapter 12 is 6
digits. So I thought I would verify that the two solutions are
equivalent by writing a 6 digit solution for chapter 9 and a 4 digit for
chapter 12.
Unfortunately, I can't seem to get a solution across the two paradigms
that is consistent.
After having read the code, I can tell that (1) the Palindrome programs
in chapters 9 and 12 solve different problems, and (2) the one in
chapter 9 generates duplicated solutions.
(1) In Palindrome_9_4, the result is required to be greater than 1000.
This enforces the leftmost digit to be nonzero. This constraint is not
present in the version of Palidrome in chapter 12.
(2) Palindrome_9_4 generates all *products* that result in palindromes.
Because the product is commutative, many of those palindromes are
generated twice. The version of chapter 12 generates all palindromes
that happen to be decomposable into a product.
The picture is even worse in fact: the version in chapter 12 cannot be
proved correct! The correctness depends on the fact that the propagator
A=:B*C guarantees the existence of a solution when A is determined. And
this is not true in general! Shame on me, I am one of the authors of
chapter 12 :-(
Here is a constraint version that solves the same problem as the
relational version in the book:
proc {Palindrome_12_4 ?A}
B C X Y
in
A::0#9999 B::0#99 C::0#99
A=:B*C
X::1#9 Y::0#9
A=:X*1000+Y*100+Y*10+X
{FD.distribute ff [X Y B C]}
end
First the leftmost digit (X) is constrained to be nonzero. Second,
distributing on B and C forces the script to effectively generate all
products that are palindromes, just like Palindrome_9_4 does.
There should be a new item in the Errata list of CTM. Thanks for
bringing this issue in the light!
Cheers,
raph
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
