Filip,
My initial thoughts were that indeed the solver was failing because I was
trying to retrieve something using an index that effectively represented
multiple values. I didn't think of creating a seperate thread which would
take action once the values were constrained. It was quite a pleasant
surprise that oz would allow you to do this and would result in the
"generate and test" algorithm.
Raphael,
Very nice formulation! =). I think the key to these types of problems is the
FD.Element constraint. I meant my pos variable to mean exactly what you did
with seq. I found it problematic to find a good name for it which I guess
resulted in the ambiguity. However, you did reverse the meaning of my Flip
by associating it with the match and not the position (and thus allowing
removal of symetries where both ends of a match have the same colour).
Thank you both for your input!
I ended up exploring another alternative completely outside of Oz by trying
the gecode library. Though it should be possible to do the same in Mozart /
Oz by implementing a custom propagator. I implemented a matrix propagator
which is initialized with a precomputed 4 dimensional matrix that specifies
which values of the four variables (pos[i] rot[i] pos[i+1] rot[i+1) are
allowed together. The propagator then enforces full consistency (ie. for any
value of a variable there must exist a combination of values of the other
variables that satisfies the constraint). The algorithm is very naive right
now and is slower than Raphael's solution. Unfortunately I don't have stats
on how many nodes are explored.
It is also possible to eliminate the symetry with multiple matches that have
the same coloured ends. This can be done by reinstating the pos variable as
the inverse of seq. Then:
%% I haven't actually compiled this...
%% Make seq and pos inverses:
for I in 1..Num do
thread
{FD.element Seq.I Pos I}
end
end
%% Create an ordering that prevents the symetry.
for I in 1..Num do
for J in 1..Num do
if Matches.I == Matches.J then
thread
Pos.I <: POS.J
end
end
end
end
Finally, I found an interesting discussion on the element propagator (in
gecode), maybe someone else will find it useful.
http://www.ps.uni-sb.de/pipermail/gecode-users/2007-January/001364.html
Cheers,
Michal
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
