整数計画法によるパズル解法 へやわけ

キューブ王

「へやわけ」パズルの求解コードを、GLPKMathProg言語で記述してみた。「へやわけ」、あるルールに従い盤面のマスを黒色にするもの。黒マス系列が盤面を分断してはならない。この「分断禁止」制約、整数計画法での記述が難しいといわれていた。しかし、巡回セールスマン問題の求解法と同様なやり方で「分断禁止」制約を素直に記述できる。

ということで、「へやわけ」の求解コードをMathProgで記述してみたもの。容易に記述できた。

 

以下は「へやわけ」の問題例()と解答例()を示している。ニコリのパズル本「へやわけ5」から。

 

 

まず、wikipediaに従い、ルールや解法を説明しておく。

--------------------------------------

[ルール]

以下のルールに従って黒マスを塗る。

(1)  数字は太線で区切られた枠(以下この枠を部屋と呼ぶ)内に入る黒マスの数である。

(2)  白マスはまっすぐの列の中で3つの部屋にまたがらない。(=太い線を2本以上またがない)

(3)  黒マスルール

(a)   黒マス同士は辺で接しない。

(b)   また、黒マスで盤面が分断されてはいけない。

 

[解法]

入口

多くの場合、へやわけを解くときに最初の手がかりになるのは、数字が入っている部屋である。

以下のような部屋は、黒マスの位置が一意に決定されるため、一般的な入口として認知されている。

A)  四隅にある2が入った2×2の部屋

B)   辺にある3が入った3×2の部屋(長さ3の辺が外枠に接している)

C)  5が入った3×3の部屋

これらの部屋はルールにより黒マスの入り方が一意的に決まる。

他に、0が入った部屋やnが入った1×(2n-1)の部屋なども黒マスが一意的に決まるが、これらは入口よりも中盤以降の手がかりになることが多い。

 A),B),C)の確定例を示しておいた。緑色の四角内の黒/白が確定し、さらに四角に隣接するマスも白に確定する(青い点で示した白マス)

 

中盤以降

中盤以降の攻略には、ルール(2)が重要な役割を果たすことが多い。ルール(3)で白マスになったマスがルール(2)を誘発して新たな黒マスを発生させる。

数字が入っている大きい部屋の一部が白マスで埋められて、通常は小さい部屋に適用される黒マスの埋め方を利用して先に進むことも多い。

---------------------------------------------

 

[類似のパズル]

このパズル、「ひとりにしてくれ」や「黒どこ」の親戚である。

 

 

左の図は「ひとりにしてくれ」パズルの問題例と解答例を示している。右の図は「黒どこ」パズルの問題例と解答例を示している。共に、ある約束に従い、いくつかのマスを黒色にする。そして「黒マスルール(3)」が制約条件となる。従って、黒マス系列が盤面を分断してはならない。この「分断禁止」制約が面白い。面白いが、整数計画法で記述するのが難しいと従来いわれていた。しかし、巡回セールスマン問題の解法と同様な解法を適用すれば、容易に記述できる。事実、「ひとりにしてくれ」や「黒どこ」は容易に記述できている。ここの「へやわけ」では、「分断禁止」制約は「黒どこ」のコードをそのまま複写して使用している。「分断禁止」制約について詳しく知りたい人は、「ひとりにしてくれ」や「黒どこ」の記事を参照すること。ここでは以降、「分断禁止」制約に詳しく触れることはない。

 

[問題の記述、重要変数、解の表現]

 盤面がいくつかの四角に分けられ、個別の四角に含まれる黒マスの数が指定される。それが問題の定義になる。15*52次元配列Ini2()がその定義例である。”1;”の行で、[1,1]から始まる1*3の四角に黒マスを2つを置けと指示している。”2:”の行で、[1,4]から始まる2*2の四角に黒マス0個を置けと指示している。なお、黒マス数9は、9個ではなくて「指定なし」という約束である(ここだけのローカルな約束)

 真ん中2つ(p1h,nh)は、横方向に限るのだが、ルール2に対応するための変数。変数Ph1は、着目するマスが、それを含む四角のどの位置に置かれているかを明示する。四角の左端かどうかで1/0が設定される。なおph1は、形式上は変数であるが、実質上は定数である。変数nhは、着目するマスが、黒か白かなどを明示する。0は黒、1,2は白を示す。1なら、黒の直後などを示す。2なら、白が続いたまま、別の四角内に進入したことを示す。白が続いて、さらに別の四角内に進入すれば3になるはずであるが、ルール(2)に対応した制約条件(s.t.)によりそれは拒否される。つまり、そこは白マスでなくて黒マスでなくてはならない。

 右のanswer(コード上はb)は、着目するマスが黒()か白()かを示す。ここの表示は、左端の問題の解答を丁度示している。

 

[求解コード]

この「へやわけ」パズル、「分断禁止」制約のやり方が分かっているとしての話だが、ルールを上手に指定できれば、特段の考察はいらないようである。そこで、いきなり解法コードの説明に入る。

 

 さて、この問題の制約条件を記述するには、その前に、マスやノードを特定するための名称系や座標系を定める必要がある。例えば、以下でいい。一般にはNr*Ncの盤面なのだが、2*2で示す。2*2の上下左右に余分にマスを追加して4*4になっている。

 

 

本来の盤面は、黄色いマス4つ(2*2)である。ノード(小さい四角)は植木算で9(3*3)である。個別の片に付けた1,1等の数値の組みは、個別片を識別する座標である。ノードは、そこを通過する斜線を識別するためのもの。dur, ddl, ddr, dulの4種ある。可能な方向4種に対応する。なおこの図は、「ひとりにしてくれ」や「黒どこ」の図をそのまま持ってきたもの。

 

以降、解法コードを順次に示していく。

 

## ----------- floor plan(heya wake) -------------------

              param Nr;

              param Nc;

              param M:= Nr+Nc;

              param R;

              param ini2{1..R,1..5} integer;   # problem definition

              var ban{1..Nr,1..Nc} >=0;        # for checking problem definition

              var b{0..Nr+1,0..Nc+1} binary; # black/not 1/0

#s.t. PROBLEM{n in 1..R}: ban[ini2[n,2],ini2[n,3]]=ini2[n,1];

 

Param Nr,Ncは盤面の行数と列数。Param Mは、分断禁止制約で使う定数。詳細略。

Param Rは、問題での部屋数。

Param ini2は、問題定義用の2次元配列。R個の部屋毎に、黒マス数、部屋の位置、大きさを明示する。詳しくは、[問題の記述、重要変数、解の表現]の節を参照。

Var banは、本質には関わらない。問題の定義を、標準の形式でダンプするためのもの。

Var bは、盤面の個別マスの黒/(1/0)を示す。これをダンプすれば、解答となる。

制約PROBLEMはコメント化されているが、個別の部屋の黒マス数を設定するもの。

 

## ------------ black rules -----------------------------

s.t. BLA0{r in 1..Nr  ,c in 2..Nc}: b[r,c-1]+b[r,c]<=1;                          # bb

s.t. BLA1{r in 2..Nr  ,c in 1..Nc}: b[r-1,c]+b[r,c]<=1;                          # bb vertical

s.t. BRA3{n in 1..R: ini2[n,1]!=9}:

              sum{r in 1..ini2[n,4],c in 1..ini2[n,5]} b[ini2[n,2]+r-1,ini2[n,3]+c-1]=ini2[n,1];

 

制約BLA0,BLA1は、ルール(3)(a)に対応。黒マス同士は辺で接しない、というもの。

制約BRA3は、ルール(1)に対応。部屋に入る黒マスの数を指定している。

 

## ------------ white rules -----------------------------

              var nh{1..Nr,1..Nc} >=0,<=2;

              var nv{1..Nr,1..Nc} >=0,<=2;

              var p1h{1..Nr,1..Nc} binary;

              var p1v{1..Nr,1..Nc} binary;

s.t. WHTh0{n in 1..R,r in 1..ini2[n,4]}: p1h[ini2[n,2]+r-1,ini2[n,3]]=1;

s.t. WHTh1{n in 1..R:ini2[n,5]!=1}:

              sum{r in 1..ini2[n,4],c in 2..ini2[n,5]} p1h[ini2[n,2]+r-1,ini2[n,3]+c-1]=0;

s.t. WHTv0{n in 1..R,c in 1..ini2[n,5]}: p1v[ini2[n,2],ini2[n,3]+c-1]=1;

s.t. WHTv1{n in 1..R:ini2[n,4]!=1}:

              sum{r in 2..ini2[n,4],c in 1..ini2[n,5]} p1v[ini2[n,2]+r-1,ini2[n,3]+c-1]=0;

 

s.t. WHIh1{r in 1..Nr}: nh[r,1]=1-b[r,1];

s.t. WHIh4{r in 1..Nr,c in 2..Nc}: nh[r,c]>=nh[r,c-1]+p1h[r,c]-3*b[r,c];

s.t. WHIh5{r in 1..Nr,c in 2..Nc}: nh[r,c]>=1-b[r,c];

s.t. WHIh6{r in 1..Nr,c in 2..Nc}: nh[r,c]<=2*(1-b[r,c]);

 

s.t. WHIv1{c in 1..Nc}: nv[1,c]=1-b[1,c];

s.t. WHIv4{r in 2..Nr,c in 1..Nc}: nv[r,c]>=nv[r-1,c]+p1v[r,c]-3*b[r,c];

s.t. WHIv5{r in 2..Nr,c in 1..Nc}: nv[r,c]>=1-b[r,c];

s.t. WHIv6{r in 2..Nr,c in 1..Nc}: nv[r,c]<=2*(1-b[r,c]);

 

s.t. OPT01{r in 2..Nr-1,c in 2..Nc-1}: b[r-1,c]+b[r,c+1]+b[r+1,c]+b[r,c-1]<=3;

 

var nh,p1hは、[問題の記述、重要変数、解の表現]節で既に説明している。白マス列の、横方向の制約を扱う。

制約WHTh0は、四角内の左端のマスに1を設定(p1h[,]=1)。実際上は、制約でなくて代入である。

制約WHTh1は、四角内の残りのマスに0を設定(p1h[,]=0)。これも制約でなくて代入。

制約WHTv0は、四角内の上端のマスに1を設定(p1v[,]=1)。実際上は、制約でなくて代入である。

制約WHTv1は、四角内の残りのマスに0を設定(p1v[,]=0)。これも制約でなくて代入。

制約WHIh1,4,5,6は、横方向でのルール(2)に対応。[問題の記述、重要変数、解の表現]節で説明した部分をコード化したもの。

制約WHIv1,4,5,6は、縦方向でのルール(2)に対応。説明略。

制約OPT01は、高速化制約。1つの白ますを4つの黒マスで囲んではならないというもの。少しは、高速化の効果があるはずである。

 

 次に「分断禁止」制約が必要だが、それは省略。その次は、求解とダンプだが、それも省略。勿論、[MathProg求解コード]節には載せている。

 

[速度]

以下の結果を得ている。P25は最後の10*10問題。P26は最初の18*10問題。

 

問題

p01 10*10

p02 1*10

p03 10*10

p04 10*10

p05 10*10

p06 10*10

p25 10*10

p26 18*10

時間sec

0.1

0.1

0.1

0.2

0.1

0.1

0.2

0.3

2.2GHz

容量MB

2.7

2.9

3.0

3.0

2.9

2.7

2.9

4.9

i7-2670QM

 

それなりに速いといえよう。但し、表に載せてないのだが、最後の18*10問題p602分以内には終わらなかった。

 

[MathProg求解コード]

 

## ----------- floor plan(heya wake) -------------------

              param Nr;

              param Nc;

              param M:= Nr+Nc;

              param R;

              param ini2{1..R,1..5} integer;   # problem definition

              var ban{1..Nr,1..Nc} >=0;        # for checking problem definition

              var b{0..Nr+1,0..Nc+1} binary; # black/not 1/0

#s.t. PROBLEM{n in 1..R}: ban[ini2[n,2],ini2[n,3]]=ini2[n,1];

## ------------ black rules -----------------------------

s.t. BLA0{r in 1..Nr  ,c in 2..Nc}: b[r,c-1]+b[r,c]<=1;                          # bb

s.t. BLA1{r in 2..Nr  ,c in 1..Nc}: b[r-1,c]+b[r,c]<=1;                          # bb vertical

s.t. BRA3{n in 1..R: ini2[n,1]!=9}:

              sum{r in 1..ini2[n,4],c in 1..ini2[n,5]} b[ini2[n,2]+r-1,ini2[n,3]+c-1]=ini2[n,1];

## ------------ white rules -----------------------------

              var nh{1..Nr,1..Nc} >=0,<=2;

              var nv{1..Nr,1..Nc} >=0,<=2;

              var p1h{1..Nr,1..Nc} binary;

              var p1v{1..Nr,1..Nc} binary;

s.t. WHTh0{n in 1..R,r in 1..ini2[n,4]}: p1h[ini2[n,2]+r-1,ini2[n,3]]=1;

s.t. WHTh1{n in 1..R:ini2[n,5]!=1}:

              sum{r in 1..ini2[n,4],c in 2..ini2[n,5]} p1h[ini2[n,2]+r-1,ini2[n,3]+c-1]=0;

s.t. WHTv0{n in 1..R,c in 1..ini2[n,5]}: p1v[ini2[n,2],ini2[n,3]+c-1]=1;

s.t. WHTv1{n in 1..R:ini2[n,4]!=1}:

              sum{r in 2..ini2[n,4],c in 1..ini2[n,5]} p1v[ini2[n,2]+r-1,ini2[n,3]+c-1]=0;

 

s.t. WHIh1{r in 1..Nr}: nh[r,1]=1-b[r,1];

s.t. WHIh4{r in 1..Nr,c in 2..Nc}: nh[r,c]>=nh[r,c-1]+p1h[r,c]-3*b[r,c];

s.t. WHIh5{r in 1..Nr,c in 2..Nc}: nh[r,c]>=1-b[r,c];

s.t. WHIh6{r in 1..Nr,c in 2..Nc}: nh[r,c]<=2*(1-b[r,c]);

 

s.t. WHIv1{c in 1..Nc}: nv[1,c]=1-b[1,c];

s.t. WHIv4{r in 2..Nr,c in 1..Nc}: nv[r,c]>=nv[r-1,c]+p1v[r,c]-3*b[r,c];

s.t. WHIv5{r in 2..Nr,c in 1..Nc}: nv[r,c]>=1-b[r,c];

s.t. WHIv6{r in 2..Nr,c in 1..Nc}: nv[r,c]<=2*(1-b[r,c]);

 

s.t. OPT01{r in 2..Nr-1,c in 2..Nc-1}: b[r-1,c]+b[r,c+1]+b[r+1,c]+b[r,c-1]<=3;

## ------------ no separation(directed graph) ----------------------

              var ddl{1..Nr+1,1..Nc+1} binary;             # down,left

              var ddr{1..Nr+1,1..Nc+1} binary;            # down,right

              var dul{1..Nr+1,1..Nc+1} binary;             # up,left

              var dur{1..Nr+1,1..Nc+1} binary;            # up,right

s.t. XX0{ r in 1..Nr+1, c in 1..Nc+1}: dur[r,c]+ddl[r,c]<=1;     # 1 direction

s.t. XX1{ r in 1..Nr+1, c in 1..Nc+1}: ddr[r,c]+dul[r,c]<=1;     # 1 direction

s.t. XX2{ r in 1..Nr+0, c in 1..Nc+0}:

                             ddr[r,c]+dur[r+1,c]+dul[r+1,c+1]+ddl[r,c+1]<=1;     # 1 arrival

s.t. SEP0{ c in 2..Nc-1}: b[1,c]=ddr[1,c];               # outer

s.t. SEP1{ c in 2..Nc-1}: b[Nr,c]=dur[Nr+1,c];                       # outer

s.t. SEP2{ r in 1..Nr-0}: b[r,1]=dur[r+1,1];                           # outer

s.t. SEP3{ r in 1..Nr-0}: b[r,Nc]=dul[r+1,Nc+1];      # outer

s.t. SEP8{ r in 1..Nr-1, c in 1..Nc}:                                     # arc

                             b[r,c]+b[r+1,c-1]<=1+dur[r+1,c]+ddl[r+1,c];

s.t. SEP9{ r in 1..Nr-1, c in 1..Nc}:                                     # arc

                             b[r,c]+b[r+1,c+1]<=1+dul[r+1,c+1]+ddr[r+1,c+1];

## ------------ no separation(arriving order) ----------------------

              var o1 {0..Nr+1,0..Nc+1} >=0, <=M;        # serial number

s.t. NUM1{ r in 0..Nr+1,c in 0..Nc+1:r=0||r=Nr+1||c=0||c=Nc+1}:o1[r,c]=1;#outer

s.t. NUM4{ r in 1..Nr, c in 1..Nc}: o1[r,c]+M*(1-ddr[r,c])    >=o1[r-1,c-1]+1;

s.t. NUM5{ r in 1..Nr, c in 1..Nc}: o1[r,c]+M*(1-dur[r+1,c])  >=o1[r+1,c-1]+1;

s.t. NUM6{ r in 1..Nr, c in 1..Nc}: o1[r,c]+M*(1-dul[r+1,c+1])>=o1[r+1,c+1]+1;

s.t. NUM7{ r in 1..Nr, c in 1..Nc}: o1[r,c]+M*(1-ddl[r,c+1])  >=o1[r-1,c+1]+1;

## ---------- solve and dump ------------------------

              var obj_value;

s.t. MINV: obj_value=

              sum{r in 2..Nr-1, c in 2..Nc-1}(ddr[r,c]+dur[r,c]+dul[r,c]+ddl[r,c])+

              0.01*sum{r in 1..Nr, c in 1..Nc}(nh[r,c]+nv[r,c]);

minimize MMM: obj_value;

solve;

 

printf "--ini2-----\n";

  for{ r in 1..R}{

    printf"%2.0f:      ",r;

    for{c in 1..5}{ printf"%2.0f ",ini2[r,c]; } printf"\n";

  }

 

printf "--answer-----\n";

for{r in 1..Nr}{ 

  printf"+";

  for{c in 1..Nc}{printf if p1v[r,c] then "--+" else "  +";

  } printf"\n";

  printf"| %s",if b[r,1] then "@" else ".";

  for{c in 2..Nc}{

              printf if p1h[r,c] then "|" else " ";

              printf" %s",if b[r,c] then "@" else ".";

  }          printf"|\n";

}

  printf"+"; for{c in 1..Nc}{printf  "--+";} printf"\n";

end;

 

 

[問題定義コード]

 

最初の2つの問題を示しておく。

 

#p01.txt

data;

param Nr:=10;

param Nc:=10;

param R :=31;

param ini2:     1       2 3     4 5:=

        1       2       1 1     2 2

        2       9       1 3     2 1

        3       2       1 4     1 3

        4       9       1 7     1 4

        5       1       2 4     1 4

        6       2       2 8     2 2

        7       1       2 10    3 1

        8       0       3 1     2 2

        9       2       3 3     3 1

        10      3       3 4     2 3

        11      9       3 7     1 1

        12      9       4 7     2 2

        13      9       4 9     1 1

        14      9       5 1     2 2

        15      9       5 4     1 3

        16      1       5 9     2 2

        17      0       6 3     4 2

        18      2       6 5     3 1

        19      2       6 6     2 2

        20      1       6 8     4 1

        21      3       7 1     3 2

        22      1       7 9     1 1

        23      9       7 10    1 1

        24      1       8 6     1 2

        25      1       8 9     2 2

        26      9       9 5     1 3

        27      9       10 1    1 3

        28      1       10 4    1 1

        29      1       10 5    1 3

        30      1       10 8    1 2

        31      9       10 10   1 1

;

end;

 

 

#p02.txt

data;

param Nr:=10;

param Nc:=10;

param R :=19;

param ini2:     1       2 3     4 5:=

        1       3       1 1     1 5

        2       1       1 6     1 3

        3       1       1 9     4 2

        4       2       2 1     3 2

        5       9       2 3     2 3

        6       9       2 6     2 3

        7       2       4 3     1 3

        8       2       4 6     2 3

        9       9       5 1     3 4

        10      9       5 5     4 1

        11      0       5 9     3 2

        12      1       6 6     3 2

        13      2       6 8     3 1

        14      9       8 1     1 2

        15      0       8 3     3 2

        16      2       8 9     3 2

        17      2       9 1     2 2

        18      9       9 5     2 2

        19      2       9 7     2 2

;

end;

 

トップページへ

 

 

Ads by TOK2