Я пытаюсь решить проблему CSP для ортогонального латинского квадрата с помощью minizinc. Это мой код:
array[1..n,1..n] of var 1..n: mat1;
array[1..n,1..n] of var 1..n: mat2;
constraint forall(i in 1..n)(alldifferent([mat1[i,j] | j in 1..n]));
constraint forall(j in 1..n)(alldifferent([mat1[i,j] | i in 1..n]));
constraint forall(i in 1..n)(alldifferent([mat2[i,j] | j in 1..n]));
constraint forall(j in 1..n)(alldifferent([mat2[i,j] | i in 1..n]));
constraint forall(i,j in 1..n)(forall(l,k in 1..n)(alldifferent([union([mat1[i,j],mat2[i,j]),union(mat1[l,k],mat2[l,k])])));
solve satisfy;
код генерирует два латинских квадрата Истинно, но для того, чтобы сделать их ортогональными, в этой строке:
constraint forall(i,j in 1..n)(forall(l,k in 1..n)(alldifferent([union([mat1[i,j],mat2[i,j]),union(mat1[l,k],mat2[l,k])])));
Мне нужно написать ограничение, которое гарантирует, что не будет двух пар, таких как [mat1(i,j),mat2(i,j)]
и [mat1(m,n),mat2(m,n)]
, которые для m!=i
и n!=j
не должны быть равными.
но код, содержащий union
, работает некорректно (или даже вызывает ошибки). Интересно, может ли кто-нибудь помочь мне с кодом этого последнего ограничения в minizinc.
Спасибо
Мой подход состоял в том, чтобы добавить следующее ограничение, чтобы гарантировать, что никакие две пары не будут одинаковыми, то есть преобразовать пары в целые числа и убедиться, что они различны.
% distinct pairs (x[i,j], y[i,j])
constraint
alldifferent([x[i,j]*n+y[i,j] | i,j in 1..n])
;
См. http://hakank.org/minizinc/latin_square_orthogonal.mzn, который также содержит некоторые ограничения симметрии.
Полная модель (включая ограничения симметрии):
include "globals.mzn";
int: n = 11;
array[1..n, 1..n] of var 1..n: x;
array[1..n, 1..n] of var 1..n: y;
solve :: int_search([x[i,j] | i,j in 1..n], occurrence, indomain_min, complete) satisfy;
constraint
forall(i in 1..n) (
all_different([ x[i, j] | j in 1..n]) /\
all_different([ x[j, i] | j in 1..n]) /\
all_different([ y[i, j] | j in 1..n]) /\
all_different([ y[j, i] | j in 1..n])
)
;
% distinct pairs (x[i,j], y[i,j])
constraint
alldifferent([x[i,j]*n+y[i,j] | i,j in 1..n])
;
% symmetry breaking
constraint
x[1,1] = 1 /\ y[1,1] = 1
;
% symmetry breaking:
% make x an "ordered" Latin square
constraint
forall(i in 1..n) (
% first row and first column: 1..n
x[1,i] = i /\
x[i,1] = i
)
/\
forall(i in 2..n) (
forall(j in 1..n) (
let {
var 0..n: tmp1 = (1+x[i-1,j]) mod n
} in
(tmp1 = 0 -> x[i,j] = n) /\
(tmp1 > 0 -> x[i,j] = tmp1)
)
)
;
output
[
"x:"
] ++
[
if j = 1 then "\n" else " " endif ++
show(x[i,j])
| i,j in 1..n
] ++
[
"\n\ny:"
] ++
[
if j = 1 then "\n" else " " endif ++
show(y[i,j])
| i,j in 1..n
]
++
[
if j = 1 then "\n" else " " endif ++
"[" ++ show(x[i,j]) ++ "," ++ show(y[i,j]) ++ "]"
| i,j in 1..n
]
++ ["\n"]
;