GLPKでの「ペントミノ」の攻略法(解法)

キューブ王

「ペントミノ」パズルの求解コードを、GLPKMathProg言語で記述してみた。「ペントミノ」、正方形5個で構成した12種の片を6*10の矩形内に詰め込むもの。過去にペントミノの求解コードを書こうとし、しかしまだ書けてなかった。そこで今回トライしたもの。一応書けたが、速度的に問題がある。なおペントミノ、2339通りの解を持つ。C言語でなら、数秒で全数求解できる。MathProgでの場合、全数求解というわけにはいかず、最初の解を求めればよしとする。

一応、求解コードを記述できた。しかし、まだ遅い。総合判断では、求解コードの記述に失敗した、ということになる。現時点の状況を記録しておく目的で、まとめておくことにしたもの。

 

[導入]

ペントミノは正方形(マスと呼ぶ場合もある)5つ結合した12種類の片を6*10の長方形に組み上げるパズルである。

 

個別の片には名前が与えられている。その1つの例では、F,I,L,という名称系である。

 

別に、O,P,Q,R,という名称系もある。最左の片、Iが相応しいのだろうが、O,P,Q,とする都合上Oとしてあるようである。

 

 

解の数は2339(反転や回転で同じ解となるものは1つと数える)。解答例も示しておいた。

手続き型言語での記述なら、深さ優先探索で各片を順に盤面に置いていく求解法でいい。片の置き方は回転と反転の組み合わせで最大8通りがある。最左の最上位を起点として片の形状表を作成する。対称解を排除するには非対称片のひとつを2方向のみとしておけばいい。 例えばCで書くなら、全数求解させても数秒で終わる。

 

[求解の範囲]

Cで書けば、全数サーチが数秒で終わると指摘している。指摘した理由は、Cでなく、整数計画法だとそういうことにはなりそうもないからである。

その前に、個別の片が回転(や反転)で最大8種の置き方が可能という部分の対応にうんざりした。Cで書くなら、単に表のエントリー数が多くなるという程度の意味だが、MathProgで書くなら、表(の記述)よりも手間が掛かる制約(の記述)数が多くなり、記述にうんざりしてしまう。

そこでサボりを考えた。全数サーチでなく1つの解サーチで満足するのなら、個別片の置き方を1つに限定してもよい。そういうサボりを早い内に決めた。

 

[問題の記述、攻略法の基本]

 上に触れたやり方で、兎に角MathProgで書いてみた。しかし1つもサーチできなかった。それで、いくつかの片の配置を予め指定しておくことにした。以下、配置(含む、予めの配置)の意味、答えのダンプ例などを説明しておく。

 

 

 左図は、1つの解答例である。個別の片に番号(1-12)が付けてある。個別の番号は5つある。その5つで片の形状を明示したことになる。例えば、左上に6番の片が置かれている。2*2の正方形にさらに1*1の正方形(マス)が右下に接続した形状であることが分かる。

 しかし、個別の片の形状を知っている前提では、個別片の最左の最上位の位置を明示するだけで、解答を示したことになる。右図の白色のマス位置を確定させるだけでいいということである。実は、今書いてあるMathProgコードのでの攻略法の基本は、白色マスの位置を確定させるものである。

 「予めの配置」とは、白色マスの配置をいくつかを、予め指定しておくもの。

 

[解法コード]

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

 

## ------------ pentomino --------------------------------

              param Nr;

              param Nc;

              param ini{1..Nr,1..Nc} integer;                # initial board

              var bbb{0..Nr+1,0..Nc+1,1..12} >=0,<=1; # bbb[r,c,k]=1<-->ban[r,c]=k

              var pos{1..Nr,1..Nc,1..12} binary;           # position

## -------------- initialize  -------------------------

s.t. INI00{r in 1..Nr,c in 1..Nc:ini[r,c]>=1}: pos[r,c,ini[r,c]]=1;

 

ここで、param Nrは盤面の行数、param Ncは盤面の列数。Param ini[,]は、予めの配置を指定するもの。

変数bbb[,,]は、盤面の3次元配列。求解用。別に2次元のban[,]がある。ダンプ用である。bbb[,,]は、筋からいえばbinaryであろうが、速度重視で>=0,<=1としてある(実数)。確か10倍は違っている。

変数pos[,,]が個別片の配置位置を示す。最重要な変数。これも>=0,<=1とできればいいのだが、そうすると頓珍漢な答えを表示してしまう。

制約INI00は、予めの指定(ini[r,c]>=1)を盤面bbb[,,]に複写するもの。

 

## -------------- basic rules  -------------------------

s.t. BAS4{r in 1..Nr,c in 1..Nc}: sum{k in 1..12} pos[r,c,k] <=1;

s.t. BAS5{k in 1..12}: sum{r in 1..Nr,c in 1..Nc} pos[r,c,k] =1;

s.t. BAS6{r in 1..Nr,c in 1..Nc}: sum{k in 1..12} bbb[r,c,k] =1;

## ------------ wall --------------------------------

s.t. W_X{r in 1..Nr,c in 1..Nc:r=1||r=Nr||c>=Nc-1}:  pos[r,c,1]=0;

s.t. W_I{r in 1..Nr,c in 1..Nc:c>=Nc-3}:                  pos[r,c,2]=0;

 …

s.t. W_T{r in 1..Nr,c in 1..Nc:r>=Nr-1||c>=Nc-1}:    pos[r,c,12]=0;

 

制約BAS4は、1つのマスに2つ以上の片が配置されてはならない、といもの。

制約BAS5は、個別片はどこかのマスに配置されるというもの。

制約BAS6は、個別のマスは、どれかの片で埋められるというもの。

制約W_X,_I,…,_Tは、個別の片が盤面から飛び出る配置にはならいことを示す。

 

## ------------ placement ---------------------------------------

s.t. P_X{r in 2..Nr-1,c in 1..Nc-2}: 5*pos[r,c,1]<=

              sum{ (ro,co) in { (0,0),(0,1),(0,2),(-1,1),(1,1)}}bbb[r+ro,c+co,1];

s.t. P_I{r in 1..Nr,c in 1..Nc-4}: 5*pos[r,c,2]<=

              sum{ (ro,co) in { (0,0),(0,1),(0,2),(0,3),(0,4)} }bbb[r+ro,c+co,2];

 …

s.t. P_T{r in 1..Nr-2,c in 1..Nc-2}: 5*pos[r,c,12]<=

              sum{ (ro,co) in { (0,0),(0,1),(0,2),(1,1),(2,1)}}bbb[r+ro,c+co,12];

 

制約P_Xは、片Xの配置位置が[r,c]であるなら、それに応じて5個のマスが片Xで埋められることを示す。

制約P_I,…P_Tも同様。勿論、片はI,…Tとなる。

 

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

              var ban{0..Nr+1,0..Nc+1} >=0,<=12;

              var pan{0..Nr+1,0..Nc+1} >=0,<=12;

              var obj_value;

s.t. CONVb{ r in 1..Nr, c in 1..Nc}: sum{ k in 1..12}k*bbb[r,c,k] =ban[r,c];

s.t. CONVp{ r in 1..Nr, c in 1..Nc}: sum{ k in 1..12}k*pos[r,c,k] =pan[r,c];

s.t. MINV: obj_value=sum{r in 1..Nr,c in 1..Nc,k in 1..12: c<=6} bbb[r,c,k];

 

maximize VALUE: obj_value;

solve;

 

printf("--ini--\n");

for {r in 1..Nr}{ 

  for{c in 1..Nc}{ printf"%3.0f",ini[r,c];} printf("\n");

}

printf("--pan--\n");

for {r in 1..Nr}{ 

  for{c in 1..Nc}{ printf"%2.0f ",pan[r,c];} printf("\n");

}

printf("--ban--\n");

for {r in 1..Nr}{ 

  for{c in 1..Nc}{ printf"%2.0f ",ban[r,c];} printf("\n");

}

end;

残りは求解(solve)とダンプ。説明は略す。

 

[ペントミノとMathProg]

 「ペントミノ」、MathProgでの記述は難しい。難しいという意味は、1つは記述量が増えてしまうというもの。後1つ、高速コードを書けそうもないというもの。

 記述量の増大は、個別片の回転(や反転)は考えず、1つの配置だけ考えるというサボりで解決(?)した。一方、高速化、かなり試行してみたが高速化できてない。予めの指定片がなければ、答えをサーチできないということ。

 

[速度など]

 現状、以下のような結果を得ている。

 

問題

p1 X,W,V

p2 X,W

p3 X,N

p4 X

p5 Y

p6

 

時間sec

0.1

2.3

9.6

351.5

-

-

2.5GHz

容量MB

2.0

2.1

2.2

2.4

-

-

2MB*2キャッシュ

 

問題p1の場合、片X,W,Vの3つを予め置いている。それで0.1sec。問題p2,p3では予め2つの片を置いている。2.3sec, 9.6secであった。問題p4は片Xだけを置いた際のもので351secである。なお、片Xは特異な形状からして、求解上からも大事な片である。この配置を指定しないと、かなり遅くなるであろう。

 

 実は、いくつかの片の配置位置を制限すれば、かなり速くなる。例えば以下。

(1)   片Uの凹を片Xの突起が埋めるという制限

(2)   片Iは行Nrにしか配置されないという制限

(3)   片Yの右上に片Lが配置されるという制限

この3つの制限(制約、最適化)を追加すれば、以下のようになった。「指定なし」を求解できている。

 

問題

p1 X,W,V

p2 X,W

p3 X,N

p4 X

p5 Y

p6

opt

時間sec

0.0

0.2

0.1

4.7

10.4

138.6

2.5GHz

容量MB

2.0

2.0

2.0

2.3

2.3

2.6

2MB*2キャッシュ

 

しかし、反則だといわれると、反論できそうもない。 以下のコードは、この最適化も入れてある。

 

[MathProg求解コード]

 

## ------------ pentomino --------------------------------

              param Nr;

              param Nc;

              param ini{1..Nr,1..Nc} integer;                # initial board

              var bbb{0..Nr+1,0..Nc+1,1..12} >=0,<=1; # bbb[r,c,k]=1<-->ban[r,c]=k

              var pos{1..Nr,1..Nc,1..12} binary;           # position

## -------------- initialize  -------------------------

s.t. INI00{r in 1..Nr,c in 1..Nc:ini[r,c]>=1}: pos[r,c,ini[r,c]]=1;

## -------------- basic rules  -------------------------

s.t. BAS4{r in 1..Nr,c in 1..Nc}: sum{k in 1..12} pos[r,c,k] <=1;

s.t. BAS5{k in 1..12}: sum{r in 1..Nr,c in 1..Nc} pos[r,c,k] =1;

s.t. BAS6{r in 1..Nr,c in 1..Nc}: sum{k in 1..12} bbb[r,c,k] =1;

## ------------ wall --------------------------------

s.t. W_X{r in 1..Nr,c in 1..Nc:r=1||r=Nr||c>=Nc-1}:  pos[r,c,1]=0;

s.t. W_I{r in 1..Nr,c in 1..Nc:c>=Nc-3}:                  pos[r,c,2]=0;

s.t. W_L{r in 1..Nr,c in 1..Nc:r=Nr||c>=Nc-2}:                       pos[r,c,3]=0;

s.t. W_Y{r in 1..Nr,c in 1..Nc:r=1||c>=Nc-2}:                         pos[r,c,4]=0;

s.t. W_U{r in 1..Nr,c in 1..Nc:r>=Nr-1||c>=Nc-1}:   pos[r,c,5]=0;

s.t. W_P{r in 1..Nr,c in 1..Nc:r=Nr||c>=Nc-1}:                       pos[r,c,6]=0;

s.t. W_N{r in 1..Nr,c in 1..Nc:r=1||c>=Nc-1}:                         pos[r,c,7]=0;

s.t. W_F{r in 1..Nr,c in 1..Nc:r<=2||c>=Nc-1}:                       pos[r,c,8]=0;

s.t. W_Z{r in 1..Nr,c in 1..Nc:r<=2||c>=Nc-1}:                       pos[r,c,9]=0;

s.t. W_W{r in 1..Nr,c in 1..Nc:r=1||r=Nr||c>=Nc-1}:  pos[r,c,10]=0;

s.t. W_V{r in 1..Nr,c in 1..Nc:r<=2||c>=Nc-1}:                       pos[r,c,11]=0;

s.t. W_T{r in 1..Nr,c in 1..Nc:r>=Nr-1||c>=Nc-1}:    pos[r,c,12]=0;

## ------------ placement ---------------------------------------

s.t. P_X{r in 2..Nr-1,c in 1..Nc-2}: 5*pos[r,c,1]<=

              sum{ (ro,co) in { (0,0),(0,1),(0,2),(-1,1),(1,1)}}bbb[r+ro,c+co,1];

s.t. P_I{r in 1..Nr,c in 1..Nc-4}: 5*pos[r,c,2]<=

              sum{ (ro,co) in { (0,0),(0,1),(0,2),(0,3),(0,4)} }bbb[r+ro,c+co,2];

s.t. P_L{r in 1..Nr-1,c in 1..Nc-3}: 5*pos[r,c,3]<=

              sum{ (ro,co) in { (0,0),(0,1),(0,2),(0,3),(1,3)}} bbb[r+ro,c+co,3];

s.t. P_Y{r in 2..Nr,c in 1..Nc-3}: 5*pos[r,c,4]<=

              sum{ (ro,co) in { (0,0),(0,1),(0,2),(0,3),(-1,1)}} bbb[r+ro,c+co,4];

s.t. P_U{r in 1..Nr-2,c in 1..Nc-2}: 5*pos[r,c,5]<=

              sum{ (ro,co) in { (0,0),(0,1),(1,0),(2,0),(2,1)}} bbb[r+ro,c+co,5];

s.t. P_P{r in 1..Nr-1,c in 1..Nc-2}: 5*pos[r,c,6]<=

              sum{ (ro,co) in { (0,0),(0,1),(1,0),(1,1),(1,2)}} bbb[r+ro,c+co,6];

s.t. P_N{r in 2..Nr,c in 1..Nc-2}: 5*pos[r,c,7]<=

              sum{ (ro,co) in { (0,0),(0,1),(-1,1),(-1,2),(-1,3)}} bbb[r+ro,c+co,7];

s.t. P_F{r in 3..Nr,c in 1..Nc-2}: 5*pos[r,c,8]<=

              sum{ (ro,co) in {(0,0),(-2,1),(-1,1),(0,1),(-1,2)}}bbb[r+ro,c+co,8];

s.t. P_Z{r in 3..Nr,c in 1..Nc-2}: 5*pos[r,c,9]<=

              sum{ (ro,co) in { (0,0),(-2,1),(-1,1),(0,1),(-2,2)}}bbb[r+ro,c+co,9];

s.t. P_W{r in 2..Nr-1,c in 1..Nc-2}: 5*pos[r,c,10]<=

              sum{ (ro,co) in { (0,0),(1,0),(-1,1),(0,1),(-1,2)}}bbb[r+ro,c+co,10];

s.t. P_V{r in 3..Nr,c in 1..Nc-2}: 5*pos[r,c,11]<=

              sum{ (ro,co) in { (0,0),(0,1),(0,2),(-1,2),(-2,2)}}bbb[r+ro,c+co,11];

s.t. P_T{r in 1..Nr-2,c in 1..Nc-2}: 5*pos[r,c,12]<=

              sum{ (ro,co) in { (0,0),(0,1),(0,2),(1,1),(2,1)}}bbb[r+ro,c+co,12];

## ------------ optimizations ----------------------------------

s.t. O_I: sum{c in 1..Nc-4} pos[Nr,c,2] =1;

s.t. O_UX{r in 1..Nr-2,c in 1..Nc-2}: pos[r,c,5]<=pos[r+1,c+1,1];

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

/* */

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

              var ban{0..Nr+1,0..Nc+1} >=0,<=12;

              var pan{0..Nr+1,0..Nc+1} >=0,<=12;

              var obj_value;

s.t. CONVb{ r in 1..Nr, c in 1..Nc}: sum{ k in 1..12}k*bbb[r,c,k] =ban[r,c];

s.t. CONVp{ r in 1..Nr, c in 1..Nc}: sum{ k in 1..12}k*pos[r,c,k] =pan[r,c];

s.t. MINV: obj_value=sum{r in 1..Nr,c in 1..Nc,k in 1..12: c<=6} bbb[r,c,k];

 

maximize VALUE: obj_value;

solve;

 

printf("--ini--\n");

for {r in 1..Nr}{ 

  for{c in 1..Nc}{ printf"%3.0f",ini[r,c];} printf("\n");

}

printf("--pan--\n");

for {r in 1..Nr}{ 

  for{c in 1..Nc}{ printf"%2.0f ",pan[r,c];} printf("\n");

}

printf("--ban--\n");

for {r in 1..Nr}{ 

  for{c in 1..Nc}{ printf"%2.0f ",ban[r,c];} printf("\n");

}

end;

 

[問題定義コード]

 

#p01.txt

data;

        param Nr:=6;

        param Nc:=10;

        param ini:

         1  2  3  4  5  6  7  8  9 10:=

  1     0  0  0  0  0  0  0  0  0  0

  2     0  0  0  0  0  0  0  0  0  0

  3     0  0  0  0  0  0  0  0  0  0

  4     0  1  0  0  0 10  0  0  0  0

  5     0  0  0  0  0  0  0  0  0  0

  6     0  0  0  0  0  0  0 11  0  0

; end;

 

#p02.txt

data;

        param Nr:=6;

        param Nc:=10;

        param ini:

         1  2  3  4  5  6  7  8  9 10:=

  1     0  0  0  0  0  0  0  0  0  0

  2     0  0  0  0  0  0  0  0  0  0

  3     0  0  0  0  0  0  0  0  0  0

  4     0  1  0  0  0 10  0  0  0  0

  5     0  0  0  0  0  0  0  0  0  0

  6     0  0  0  0  0  0  0  0  0  0

; end;

 

#p03.txt

data;

        param Nr:=6;

        param Nc:=10;

        param ini:

         1  2  3  4  5  6  7  8  9 10:=

  1     0  0  0  0  0  0  0  0  0  0

  2     0  0  0  0  0  0  0  0  0  0

  3     0  0  0  0  0  0  0  0  0  0

  4     0  1  0  0  0  0  0  0  0  0

  5     0  0  0  0  0  0  0  0  0  0

  6     0  0  0  0  0  7  0  0  0  0

; end;

 

#p04.txt

data;

        param Nr:=6;

        param Nc:=10;

        param ini:

         1  2  3  4  5  6  7  8  9 10:=

  1     0  0  0  0  0  0  0  0  0  0

  2     0  0  0  0  0  0  0  0  0  0

  3     0  0  0  0  0  0  0  0  0  0

  4     0  1  0  0  0  0  0  0  0  0

  5     0  0  0  0  0  0  0  0  0  0

  6     0  0  0  0  0  0  0  0  0  0

; end;

 

#p05.txt

data;

        param Nr:=6;

        param Nc:=10;

        param ini:

         1  2  3  4  5  6  7  8  9 10:=

  1     0  0  0  0  0  0  0  0  0  0

  2     0  0  0  0  4  0  0  0  0  0

  3     0  0  0  0  0  0  0  0  0  0

  4     0  0  0  0  0  0  0  0  0  0

  5     0  0  0  0  0  0  0  0  0  0

  6     0  0  0  0  0  0  0  0  0  0

; end;

 

 

#p06.txt

data;

        param Nr:=6;

        param Nc:=10;

        param ini:

         1  2  3  4  5  6  7  8  9 10:=

  1     0  0  0  0  0  0  0  0  0  0

  2     0  0  0  0  0  0  0  0  0  0

  3     0  0  0  0  0  0  0  0  0  0

  4     0  0  0  0  0  0  0  0  0  0

  5     0  0  0  0  0  0  0  0  0  0

  6     0  0  0  0  0  0  0  0  0  0

; end;

 

 

トップページへ

 

 

Ads by TOK2