Задача ортогонального латинского квадрата с Minizinc

Я пытаюсь решить проблему 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. Спасибо


constraints algorithm minizinc
person S.Fadaei    schedule 12.12.2020    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Мой подход заключался в том, чтобы добавить следующее ограничение, чтобы гарантировать, что никакие две пары не совпадают, т.е. преобразовать пары в целые числа и гарантировать, что они различны.

% 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"]

      ;
person hakank    schedule 12.12.2020