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

キューブ王

前回、「ペントミノ」パズルの求解コードにトライした。一応、求解コードを記述できた。のだが、「求解コードの記述に失敗している」と主張されると、反論できない部分があった。

そこで今回、再度挑戦したもの。ある程度、求解コードの記述に成功した。そのコードを提示する。また、Cコードも提示する。

最初の方は、前回の記事からの抜粋になる。

 

[導入]

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

 

image001

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

 

image003

 

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

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

 

[求解の範囲]

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

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

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

 

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

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

 

image004

 

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

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

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

 

[前回の結果]

 以下のような結果を得ている。反則の最適化を入れない場合のもの。

 

問題

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は特異な形状からして、求解上からも大事な片である。この配置を指定しないと、かなり遅くなるであろう。

 問題p5p6を求解できなかった。そこで、苦肉の策で、いくつかの片の配置位置を制限した。

(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キャッシュ

 

以上、前回の記事の抜粋。

 

[新規導入の最適化] 

 そこで今回、高速化にトライするもの。というか、前回の失敗以降、思い出しては高速化のことを考えていて、しかし旨くいかなかった。今回、本格的に考えてみたもの。実際は、本格的に試行錯誤したというのが正しい。

Cコードのやり方だと、左側から、さらに最上位から片を詰めていくのだが、これと同様なことをMathprogに強制できれば旨く行く気がした。そこで以下のような最適化を考えた。

(1)   s.t. O_1: sum{k in 1..12} pos[1,1,k] =1;

(2)   s.t. O_2: sum{r in 1..Nr, k in 1..12} pos[r,1,k] >=3;

(3)   s.t. O_3: sum{c in 1..Nc, k in 1..12} pos[1,c,k] >=3;

(4)   s.t. O_4: sum{c in Nc-1..Nc, k in 1..12} pos[1,c,k] =0;

(5)   s.t. O_5: sum{c in 1..6}(pos[1,c,2]+pos[6,c,2]) =1;

(6)   s.t. O_6: sum{r in 1..6} pos[r,8,5] =0;

最初の(1)は、どれかの片が、位置[1,1]に置かれるというもの。

次の(2)は、最左の位置[r,1]に3つ以上の片が置かれるというもの。

次の(3)は、最上位の位置[1,c]3つ以上の片が置かれるというもの。

次の(4)は、右上[1,9]or[1,10]には片を置けないというもの。

次の(5)は、最上位[1,c]または最下位[6,c]に片Iが置かれるといもの。

次の(6)は、最右[r,8]に片Uは置けないというもの。

なお、(1),(2),(3)が、左側の最上位から片を詰めていく強制(orお願い)を想定したものである。

別に以下のもの。

(7)           var bin2{1..Nr,1..Nc} binary;

s.t. BAS7{r in 1..Nr,c in 1..3,k in 1..12}: bbb[r,c,k]<=bin2[r,c];

s.t. MINV: obj_value=sum{r in 1..Nr,c in 1..Nc} bin2[r,c];

minimize VALUE: obj_value;

この(7)、左側の方に、早いうちに片を詰めていくように強制させるつもりだったのであろう。が、色々と試した結果でてきたもので、何が起こるのか、当方にはさっぱり分からない。

 

そして、(7)以外の最適化を、コードの上の方に置いて走行してみた。すると予めの指定なしで解を得ることができた。勿論、前回の最適化は全て削除してある。

 

問題

p1 X,W,V

p2 X,W

p3 X,N

p4 X

p5 Y

p6

時間sec

0.1

0.3

0.6

2.3

7.5

126.4

2.2GHz

容量MB

2.3

2.4

2.4

2.6

2.8

3.0

i7-2670QM

 

[解法コード]

前節で説明した部分以外は、前回のコードと同じ筈であり、細かい説明はしない。ただし、ダンプ部分の1つを説明しておく。

 

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

for {r in 1..Nr}{ 

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

# for{c in 1..Nc}{ printf"%2s ",substr("XILYUPNFZWVT",ban[r,c],1);} printf("\n");

}

 

Banのダンプ部分である。コメント化してあるfor文、最初の方で示した名称系に従う文字で盤面をダンプしようとしたもの。しかし、ban[r,c]が整数ではないものがあると指摘され、

旨くダンプできない。ということでコメント化したもの。

 

 

[MathProg求解コード その2]

 

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

           param Nr;

           param Nc;

           param ini{1..Nr,1..Nc} integer;                  # problem 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

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

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

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

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

s.t. O_1: sum{k in 1..12} pos[1,1,k] =1;

s.t. O_2: sum{r in 1..Nr, k in 1..12} pos[r,1,k] >=3;

s.t. O_3: sum{c in 1..Nc, k in 1..12} pos[1,c,k] >=3;

s.t. O_4: sum{c in Nc-1..Nc, k in 1..12} pos[1,c,k] =0;

s.t. O_5: sum{c in 1..6}(pos[1,c,2]+pos[6,c,2]) =1;

s.t. O_6: sum{r in 1..6} pos[r,8,5] =0;

## -------------- 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;

s.t. BAS7{r in 1..Nr,c in 1..3,k in 1..12}: bbb[r,c,k]<=bin2[r,c];

## ------------ 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];

## ---------- 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} bin2[r,c];

 

minimize VALUE: obj_value;

solve;

 

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

for {r in 1..Nr}{ 

  for{c in 1..Nc}{ printf"%2.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");

# for{c in 1..Nc}{ printf"%2s ",substr("XILYUPNFZWVT",ban[r,c],1);} 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;

 

 

[Cコード]

 C言語によるアルゴリズム事典」内の、テトロミノの箱詰めコードを参考にして作ったもの。細かい説明はしない。

今あるパソコンでcygwin走行すると、2secで全数求解できている。

 

// ------------           pentomino --------------------------

#include <stdio.h>

#include <stdlib.h>

#define Pieces      12 

#define Col         6 

#define Row         10 

#define PieceSize   5 

#define MaxSymmetry 8 

#define MaxSite     ((Col+1)*Row -1)

#define LimSite     ((Col+1)*(Row+1))

#define W '*'     // wall

#define S ' '       // space,vacant

char board[LimSite]={

S,S,S,S,S,S,W, S,S,S,S,S,S,W, S,S,S,S,S,S,W, S,S,S,S,S,S,W, S,S,S,S,S,S,W,

S,S,S,S,S,S,W, S,S,S,S,S,S,W, S,S,S,S,S,S,W, S,S,S,S,S,S,W, S,S,S,S,S,S,W,

W,W,W,W,W,W,W};

char name[Pieces]={'X','I','L','Y','U','P','N','F','Z','W','V','T'};

int symmetry[Pieces]={1,2,2,8,4,8,8,8,4,4,4,4};

int rest[Pieces]={1,1,1,1,1, 1,1,1,1,1, 1,1};

int shape[Pieces][MaxSymmetry][PieceSize-1]={

{{6,7,8,14 } } ,                                                              // X

{{7,14,21,28 },{1,2,3,4 } },                                              // I

{{1,7,14,21 },{7,8,9,10 } },                                              // L

{{7,8,14,21 }, {6,7,8,9 }, {7,13,14,21}, {1,2,3,9 },                

 {6,7,14,21 }, {1,2,3,8 }, {7,14,15,21}, {5,6,7,8 }      },          // Y

{{1,7,14,15 }, {2,7,8,9 }, {1,8,14,15 }, {1,2,7,9 }       },          // U

{{1,7,8,14 }, {1,7,8,9 },{6,7,13,14 }, {1,2,8,9 },

 {1,7,8,15 }, {1,2,7,8 },{7,8,14,15 }, {1,6,7,8 }         },          // P

{{7,14,15,22},{1,5,6,7 },{7,8,15,22 },{1,2,6,7 },

 {7,13,14,20},{1,2,9,10},{6,7,13,20 },{1,8,9,10 }       },          // N

{{1,8,9,15  },{6,7,8,13 },{6,7,14,15 },{5,6,7,13 },

 {1,6,7,14  },{7,8,9,15 },{7,8,13,14 },{6,7,8,15 }      },          // F

{{1,8,15,16 },{5,6,7,12 },{1,7,13,14 },{7,8,9,16 }       },          // Z

{{7,8,15,16 },{6,7,12,13 },{1,8,9,16 },{1,6,7,13 }       },          // W

{{1,2,7,14 }, {7,14,15,16},{7,12,13,14},{1,2,9,16}      },          // V

{{7,8,9,14 }, {7,13,14,15},{5,6,7,14 },{1,2,8,15 }       }           // T

};

static int count = 0;

void found(void)

{           int i, j;

//        if(++count>10) return;

           if(++count%100!=0) return;

           printf("\nans: %d\n\n", count);

           for (i=0; i<Col; i++,         printf("\n"))

                       for (j=i; j<MaxSite; j+=Col+1) printf("%c", board[j]);

}

void try(int site)

{           int piece,state;

           for (piece = 0; piece < Pieces; piece++) {

                       if (rest[piece] == 0) continue;

                       rest[piece]--;

                       for (state = 0; state < symmetry[piece]; state++) {

                                  int s0, s1, s2, s3,temp;

                                  s0 = site + shape[piece][state][0];

                                  s1 = site + shape[piece][state][1];

                                  if (board[s0] !=S)            continue;

                                  if (board[s1] !=S)            continue;

                                  s2 = site + shape[piece][state][2];

                                  s3 = site + shape[piece][state][3];

                                  if (board[s2] !=S)            continue;

                                  if (board[s3] !=S)            continue;

 

                                  board[site]=board[s0]=board[s1]=board[s2]=board[s3]

                                                                    = name[piece];

                                  temp = site;

                                  while (board[++temp] != S) ;

                                  if (temp < MaxSite){         try(temp); }

                                  else{                             found(); }

                                  board[site]=S; board[s0]=S; board[s1]=S;

                                  board[s2]=S; board[s3]=S;

                       }

                       rest[piece]++;

           }

}

int main()

{           try(0);

           printf("count=%d\n",count);

           exit(0);

}

 

 

トップページへ

 

Ads by TOK2