対称方陣

チラシの裏

ある現実の問題について考えていると、次のようなパズルと等価であることに気づいた。

  1. Nは偶数
  2. N x Nの行列の対角線を含まない上三角行列部分を、1からN-1の整数で全て埋める。(それぞれの値をN/2回使用)
  3. 埋めた値を下三角行列の対称位置にコピーする。
  4. 行列の全ての行、全ての列で、同じ値は一回しか現れないようにする。(下三角も含めて一回)

N=6の場合、以下のような答えになる。

   4 5 3 2 1
     3 2 1 5
       1 4 2
         5 4
           3

ラテン方陣というものに似ているみたいだが、対称行列が条件になっている所が違う。
Sugar制約ソルバーを使って解いてみると、N=50の場合でも85sec.で答えを出した。(PicoSAT ver.846をSAT Solverとして使用したとき)
N=50だと、変数の数が1225(= N*(N-1)/2)になるが、この程度の時間で解けるので驚いた。


(例) N=6のときの制約ルール

; Match N=6
(int x00_01 1 5)
(int x00_02 1 5)
(int x00_03 1 5)
(int x00_04 1 5)
(int x00_05 1 5)
(int x01_02 1 5)
(int x01_03 1 5)
(int x01_04 1 5)
(int x01_05 1 5)
(int x02_03 1 5)
(int x02_04 1 5)
(int x02_05 1 5)
(int x03_04 1 5)
(int x03_05 1 5)
(int x04_05 1 5)

(alldifferent        x00_01 x00_02 x00_03 x00_04 x00_05)
(alldifferent x00_01        x01_02 x01_03 x01_04 x01_05)
(alldifferent x00_02 x01_02        x02_03 x02_04 x02_05)
(alldifferent x00_03 x01_03 x02_03        x03_04 x03_05)
(alldifferent x00_04 x01_04 x02_04 x03_04        x04_05)
(alldifferent x00_05 x01_05 x02_05 x03_05 x04_05       )
; END