Hello Martin,
> Hence my questions: is it possible to use LDSB to implement symmetry
> breaking "toroidal"? If not, is it possible to implement symmetry
> breaking "toroidal" in another way?
You can use LDSB to break this symmetry, which is the composition of
two "cyclic" symmetries. If your variables are in a matrix "m":
Symmetries syms;
IntVarArgs rows;
for (int r = 0; r < m.height(); r++)
rows << m.row(r);
for (int r = 0; r < m.height(); r++)
rows << m.row((r+1) % m.height());
syms << VariableSequenceSymmetry(rows, m.width()*m.height());
IntVarArgs cols;
for (int r = 0; r < m.width(); r++)
cols << m.col(r);
for (int r = 0; r < m.width(); r++)
cols << m.col((r+1) % m.width());
syms << VariableSequenceSymmetry(cols, m.width()*m.height());
The idea is that for the rows you have a variable sequence symmetry,
where the variables in the first sequence map to the corresponding
variables in the second one:
a b c d e f g h i j k l m n o p
e f g h i j k l m n o p a b c d
(i.e. a -> e, b -> f, etc.)
And similar for the columns.
Another way to break the symmetry, without LDSB, is to fix the position
of the smallest element; e.g. force the smallest element to be in the
top-left corner. You can do this by posting constraints
m(0,0) <= m(0,1)
m(0,0) <= m(0,2)
etc.
Are the variables in the square array constrained to be all different?
If so, you can strengthen those constraints into "strictly less than".
If they're all different and form a permutation (i.e. the number of
values in their domain is equal to the number of variables) then you
can simply fix the top-left variable to the smallest value;
e.g. "m(0,0) = 1".
Cheers,
Chris
_______________________________________________
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
