Dear Mark,
The trick is to constrain "EF" to be the smallest factor in the product.
Palindromes you find are duplicated because swaping the factors in the
product gives the same palindrome. Simply restrict the search space to
avoid that.
I suggest to first simplify a bit your model. In my view, only 4
variables are relevant to the problem: the first two digits in the
palindrome (say A and B), and the factors of the product (say X and Y).
Those variables are constrained as:
[A B] ::: 0#9 % those are digits
[X Y] ::: 0#99 % those are two-digit numbers
A >: 0 % A is nonzero
1001*A + 110*B =: X*Y % ABBA is equal to X * Y
X =<: Y % break symmetry
I would define the solution as:
sol([A B B A] X Y)
Note that duplicates may still appear, but this time because the
factorization of the palindrome might not be unique. For instance, the
palindrome 1001 will appear twice because it admits two factorizations:
1001 = 11*91 = 13*77
Cheers,
raph
mark richardson wrote:
Hi,
I'm working through various tutorials on FD constraints and developed
the following program
++++++++++++++++++++++
%find all palindromic numbers of four digits that
%are the product of two digit numbers
declare
Palindrome
Results
proc {Palindrome Root}
A B C D E F G H %A-D are the palindrome digits
%E/F and G/H are the factors of the palindrome
in
Root=sol(a:A b:B c:C d:D e:E f:F g:G h:H)%set up the solution record
Root ::: 0#9 %all elements of Root are digits from 0 to 9
A \=:0 %palindrome can't begin with 0
A =: D %first digit must match last
B =: C %second digit must match third
(10* E + F) * (10 * G + H) =: A*1000 + B*100 + C*10 + D
%the product of the two digit numbers EF and GH must
%equal the number ABCD
{FD.distribute ff Root} %distribute Root using 'first-fail'
end
fun {Results L} %just to 'pretty-print' results
case L of H|T then
{VirtualString.toAtom {IntToString (10* H.e)+H.f}#" * "#
{IntToString (10*H.g)+H.h}#" = "#
{IntToString (1000*H.a)+(100*H.b)+(10*H.c)+H.d}}|{Results T}
else
nil
end
end
{Browse {Results{SearchAll Palindrome}}} %searchall solutions
%NB Display parameters under options in browser need changing
%to large browse limit to see all solutions
%118 in total
+++++++++++++++++++++++
the program works fine up to a point in that it produces all the correct
palindromes. However, half of them are duplicates.
Can anyone tell me how to approach avoiding symmetries in this case?
Any help would be great...
Mark Richardson
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
