Minizinc 的正交拉丁方问题

Question

我正在尝试使用 minizinc 解决正交拉丁方问题的 CSP。这是我的代码：

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 中的最后一个约束代码。谢谢

Answer 1

我的方法是添加以下约束以确保没有两对是相同的，即将这些对转换为整数并确保它们是不同的。

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

      ;

Minizinc 的正交拉丁方问题

Orthogonal Latin Square Problem with Minizinc

algorithm

constraints

minizinc