Dear Michal,
Here is a slightly different solution. It uses the inverse of your
vector Pos, i.e., it gives the sequence of match numbers.
It also creates three intermediary vectors: the left and right color of
each match after it has been possibly flipped, and the whole sequence of
colors, where adjacent colors are equal two by two. We then use the
propagator FD.element to link the sequence numbers with the colors in
the sequence.
These intermediate variables provide better propagation, because it
allows to represent explicitly information like: "the third match cannot
have its left color equal to 2". If this occurs, it immediately
restrict the possible values for the 2nd and 3rd matches in the sequence.
BTW, I have eliminated a symmetry that occurs in Filip's solution: when
a match has two same colors, you never flip it. My solver find 20
solutions with only 40 failed nodes in the search tree.
Have fun,
raph
declare
%% Our matches, where each match has different coloured ends.
%% Different colours represented by different numbers. Note that
%% the matches are given in an order that provides a solution:
%% 0---1 1---0 0---2 2---2 2---0
%%
%% This is equavalent to the solution (see code):
%% solution(flip:flip(0 0 0 0 0) pos:pos(1 2 3 4 5))
%%
%% Another solution might be:
%% 1---0 0---2 2---2 2---0 0---1
%%
%% This is equavalent to the solution (see code):
%% solution(flip:flip(1 1 0 0 0) pos:pos(1 5 2 3 4))
%%
M = matches(match(0 1)
match(1 0)
match(0 2)
match(2 2)
match(2 0))
Num = {Width M}
proc {EqualTwoByTwo L}
case L of X|Y|T then X=Y {EqualTwoByTwo T} else skip end
end
proc {Solver Sol}
%% for each match, whether it is flipped, and its left and right
%% color after the flip
Flip={FD.tuple flip Num 0#1}
Left={FD.tuple left Num 0#2}
Right={FD.tuple right Num 0#2}
%% sequence of match numbers (inverse of Pos)
Seq={FD.tuple seq Num 1#Num}
%% sequence of match colors
ColSeq={FD.tuple col 2*Num 0#2}
Vars = {FoldL {Map [Flip Left Right Seq ColSeq] Record.toList} Append nil}
in
Sol = solution(seq:Seq flip:Flip)
%% first define the flip of each match
for I in 1..Num do
match(A B) = M.I
in
if A==B then
Flip.I = 0
Left.I = Right.I = A
else
[Left.I Right.I] ::: [A B]
{FD.distinct [Left.I Right.I]}
Flip.I = (Left.I =: B)
end
end
%% now define the sequence of matches
{FD.distinct Seq}
{EqualTwoByTwo {Record.toList ColSeq}.2}
for I in 1..Num do
thread
%% the match number Seq.I has its left color in
%% ColSeq.(2*I-1) and its right color in ColSeq.(2*I)
{FD.element Seq.I Left ColSeq.(2*I-1)}
{FD.element Seq.I Right ColSeq.(2*I)}
end
end
{FD.distribute ff Vars}
end
{ExploreOne Solver}
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
