整数計画法によるパズル解法 シャカシャカ

キューブ王

「シャカシャカ」パズルの求解コードを、GLPKMathProg言語で記述してみた。「シャカシャカ」、マスに黒い三角形を置いていくパズルである。

以下は「シャカシャカ」の問題例()と解答例()を示している。ニコリのお試し問題から。

 

 

wikipediaにはシャカシャカは記載されてないので、ニコリの公式ガイドブックに従い、ルールを説明しておく。

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

シャカシャカは、マスに黒い三角形を置いていくパズルです。

[ルール]

1. 盤面のいくつかの白マスを三角形に黒くぬりつぶしましょう。

2. マスのぬり方は、4通りのいずれかです。

3. 盤面の数字は、その数字の入っているマスにタテヨコに隣り合うマスのうち、 三角形にぬるマスの数を表しています。

4. ぬられずに白く残った部分は、すべて長方形(正方形も含む)にならなければなりません。

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

 シャカシャカというパズルがあるのは昔から知っていたのだが、黒い3角形の扱いが面倒そうで、攻略(解法のコード化)しないままであった。

しかし、ちょっと考えて、黒い三角形の扱いは問題にならなくて、容易に攻略できることが分かった。そして、実際に攻略してみた、というもの。

 

[攻略法の概要]

「白く残った部分が長方形になる」というルール4を的確に表現できれば、全てが解決する。まず、マスの個別種に名前を与える。

 

gpは、p型灰色という程度の意味。gqは、q型灰色。以下略。

そして、解答図中の、白く残った部分をよく観察する。

この図では、2つの白い長方形の辺の部分に矢印を置いている。白を右に眺めつつ長方形の辺を辿る矢印群である。

上の傾いた長方形(以下ダイアモンド型)の場合、p型の次には直進してp型か折れ曲がってq型が来る。q型の次には、直進してq型か折れ曲がってd型が来る。以下、略。

下の傾いてない長方形の場合、矢印の左は黒い辺、右は白マスとなる。そして右向き矢印の次は、直進して右向き矢印か折れ曲がって下向き矢印が来る。下向き矢印の次は、直進して下向き矢印か折れ曲がって左向き矢印が来る。以下、略。

今、指摘した部分をそのままコード化すれば、シャカシャカは容易に解けることになる。

 

[攻略法]

そこで、攻略法を説明する。

 

## ----------- shakashaka -------------------

         param Nr;

         param Nc;

         param ini{1..Nr,1..Nc} integer;               # board to define problem

## ------------ initialization ---------------------------

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

         var g{0..Nr+1,0..Nc+1} binary;                         # 1/0: gray/not

         var w{0..Nr+1,0..Nc+1} binary;                         # 1/0: white/not

         var gp{0..Nr+1,0..Nc+1} binary;                        # p' type gray

         var gq{0..Nr+1,0..Nc+1} binary;                        # 'q type gray

         var gb{0..Nr+1,0..Nc+1} binary;                        # b, type gray

         var gd{0..Nr+1,0..Nc+1} binary;                        # ,d type gray

s.t. ALL00{r in 0..Nr+1,c in 0..Nc+1}: b[r,c]+g[r,c]+w[r,c]=1;

s.t. WALL0{r in 0..Nr+1,c in 0..Nc+1:r=0||r=Nr+1||c=0||c=Nc+1}: b[r,c]=1;

s.t. INI3{r in 1..Nr,c in 1..Nc:ini[r,c] =8}: b[r,c]=0;

 

さて、param Nrは問題の盤面の行数、param Ncは列数である。

Param ini[,]は、問題定義配列。最初の図の左図のような問題を与える。具体的に与えた例はこのページ最後尾の問題を参照。

変数b[,],g[.],w[,]は、盤面の個別マスの黒、灰、白を与えるもの。変数gp[,],gq[,],gb[,],bd[,]は、灰色の種別を与えるもの。p型、q型、b型、d型。

制約ALL00は、個別のマスは黒か灰か白であること(ルール1)を示す。

制約WALL0は、盤面の拡大部分(r=0||r=Nr+1||c=0||c=Nc+1)に、黒を設定したもの。

制約INI3は、問題定義で黒でない(8で代用)マスは、黒とはならないこと(ルール1)を明示したもの。

 

## ------------ gray rules -----------------------------

         var indx{1..Nr,1..Nc} >=1,<=5;

s.t. GRAY0{r in 1..Nr,c in 1..Nc:ini[r,c]<=4}: g[r-1,c]+g[r,c+1]+g[r+1,c]+g[r,c-1]=ini[r,c];

s.t. GRAY2{r in 1..Nr,c in 1..Nc:ini[r,c] =8}: g[r,c]=gp[r,c]+gq[r,c]+gb[r,c]+gd[r,c];

s.t. INDEX{r in 1..Nr,c in 1..Nc}: indx[r,c]= 1+gd[r,c]+2*gb[r,c]+3*gp[r,c]+4*gq[r,c];     # indx: for dump

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

s.t. BLCK0{r in 1..Nr,c in 1..Nc:ini[r,c]<=5}: b[r,c]=1;

 

制約GRAY0は、数字指定の黒マスの周りに、指定数字個数の灰色マスが置かれる制約(ルール3)

制約GRAY2は、問題定義で黒でない(8で代用)マスが灰色マスであれば、p型、q型、b型、d型のどれかになる(ルール2)点を明示。

制約INDXは、実際は制約でなく代入。ダンプ用のインデックス計算。

制約BLK0は、数字指定のマス(ini[r,c]<=5)は黒となることを示している。

 

## ------------ arrows for constructing a diamond -----------------------------

s.t. P00{r in 1..Nr,c in 1..Nc}: gp[r,c-1]<=0.5*(gp[r-1,c]+w[r,c])+gq[r,c];                # p

s.t. Q00{r in 1..Nr,c in 1..Nc}: gq[r-1,c-1]<=0.5*(gq[r,c]+w[r,c-1])+gd[r,c-1];            # q

s.t. D00{r in 1..Nr,c in 1..Nc}: gd[r-1,c]<=0.5*(gd[r,c-1]+w[r-1,c-1])+gb[r-1,c-1];        # d

s.t. B00{r in 1..Nr,c in 1..Nc}: gb[r,c]<=0.5*(gb[r-1,c-1]+w[r-1,c])+gp[r-1,c];            # b

 

制約P00,Q00,D00,B00は、[攻略法の概要]節内のダイヤモンドの説明部分をコード化したもの。

制約P00は、詳しく説明しておく。着目マス[r,c]の左がp(gp[r,c-1])なら、上がp型で自分[r,c]は白である(0.5*(gp[r-1,c]+w[r,c])。または、q型である(gq[r,c])

 

## ------------ arrows for constructing a rectangle -----------------------------

s.t. BW00{r in 1..Nr+1,c in 1..Nc+1}: b[r-1,c-1]+gb[r-1,c-1]+gd[r-1,c-1]+w[r,c-1]<=        # bb -->

         1+0.5*(b[r-1,c]+gb[r-1,c]+gd[r-1,c]+w[r,c])+(b[r,c]+gb[r,c]+gp[r,c]);             # ww

s.t. BW01{r in 1..Nr+1,c in 1..Nc+1}: w[r-1,c-1]+b[r-1,c]+gb[r-1,c]+gp[r-1,c]<=            #     wb v

         1+0.5*(w[r,c-1]+b[r,c]+gb[r,c]+gp[r,c])+(b[r,c-1]+gp[r,c-1]+gq[r,c-1]);           #     wb v

s.t. BW02{r in 1..Nr+1,c in 1..Nc+1}: w[r-1,c]+b[r,c]+gp[r,c]+gq[r,c]<=                        # <-- ww

         1+0.5*(w[r-1,c-1]+b[r,c-1]+gp[r,c-1]+gq[r,c-1])+(b[r-1,c-1]+gq[r-1,c-1]+gd[r-1,c-1]); #     bb

s.t. BW03{r in 1..Nr+1,c in 1..Nc+1}: b[r,c-1]+gq[r,c-1]+gd[r,c-1]+w[r,c]<=                  # bw  A

         1+0.5*(b[r-1,c-1]+gq[r-1,c-1]+gd[r-1,c-1]+w[r-1,c])+(b[r-1,c]+gd[r-1,c]+gb[r-1,c]); # bw  A

 

制約BW00,BW01,BW02,BW02は、[攻略法の概要]節内の傾いてない長方形の説明部分をコード化したもの。

制約BW00は詳しく説明しておく。着目マス[r,c]の左上が黒い辺(b[r-1,c-1] +gb[r-1,c-1] +gd[r-1,c-1])で、左が白(w[r,c-1])なら、上も黒い辺(0.5*(b[r-1,c] +gb[r-1,c] +gd[r-1,c]))で、自分は白(w[r,c])である。または、自分が黒い辺(b[r,c]+gb[r,c]+gp[r,c])である。

 

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

s.t. BE0001{r in 1..Nr+0,c in 1..Nc+0}: b[r,c-1]+gd[r,c-1]+gq[r,c-1]<=0.5*(1-gq[r,c]+1-gd[r,c]);     # Bx,dx,qx

s.t. BE0002{r in 1..Nr+0,c in 1..Nc+0}: b[r,c+1]+gb[r,c+1]+gp[r,c+1]<=0.5*(1-gp[r,c]+1-gb[r,c]);     # xB,xb,xp

s.t. BE0003{r in 1..Nr+0,c in 1..Nc+0}:                                           # B b d

                  b[r-1,c]+gb[r-1,c]+gd[r-1,c]<=0.5*(1-gb[r,c]+1-gd[r,c]);        # y,y,y

s.t. BE0004{r in 1..Nr+0,c in 1..Nc+0}:                                           # y y y

                  b[r+1,c]+gp[r+1,c]+gq[r+1,c]<=0.5*(1-gp[r,c]+1-gq[r,c]);        # B,p,q

 

ここの制約は、個別マスの可能な型を限定するもの。なくてもいい気もするが、高速化のために入れてある。1つ説明しておく。

制約BE0001は、自分の左に黒い辺(b[r,c-1] +gd[r,c-1] +gq[r,c-1])があれば、自分はq型ではありえず(1-gq[r,c])d型でもありえない(1-gd[r,c])というもの。

 

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

         var obj_value;

s.t. minv: obj_value=sum{r in 1..Nr-0, c in 1..Nc-0} g[r,c];

maximize mmm: obj_value;

solve;

 

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

for {r in 1..Nr+0}{ 

  for{c in 1..Nc+0}{ printf"%s",if ini[r,c]=8 then"."else "B";

                     printf"%s",if ini[r,c]=8 then "." else ini[r,c];

         } printf("\n");

} printf("\n");

 

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

for {r in 1..Nr+0}{ 

  for{c in 1..Nc+0}{       printf"%s",if b[r,c] then"BB"else substr("===/\=P/\q",2*indx[r,c]-1,2);

         } printf("\n");

  for{c in 1..Nc+0}{       printf"%s",if b[r,c] then"BB"else substr("==/db\/==\",2*indx[r,c]-1,2);

         } printf("\n");

} printf("\n");

end;

 

最後に、solveとダンプ。ダンプは少し説明しておく。ダンプで以下のように表示される(左の2つ)

ソースコードやダンプ結果で“¥”となっている文字、cygwinなどでは逆割り(“/”の左右反転形)になる場合が多い(右、図として横幅も広げている)。それを期待している。しかしMSワードやパワーポイントでは”\”となってしまう場合が多い。フォント絡みの問題である。

そういうこともあり、最後尾のコードには逆割りをY“で代用したコードも入れてある。

 

[速度]

お試し問題の最初の6個で走行実験。全て正解した(と思う)。以下の結果を得ている。

 

問題

p01 10*10

p02 10*10

p03 10*10

p04 10*18

p05 10*18

p06 10*18

時間sec

0.0

0.0

0.0

0.0

0.0

0.0

2.2GHz

容量MB

2.1

2.1

2.2

3.4

3.4

3.4

i7-2670QM

 

全て0.0secとなった。極端に速い。というか、このシャカシャカ、コンピュータが極端に得意なパズルといえよう。

 

[解法コード]

 

## ----------- shakashaka -------------------

         param Nr;

         param Nc;

         param ini{1..Nr,1..Nc} integer;               # board to define problem

## ------------ initialization ---------------------------

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

         var g{0..Nr+1,0..Nc+1} binary;                         # 1/0: gray/not

         var w{0..Nr+1,0..Nc+1} binary;                         # 1/0: white/not

         var gp{0..Nr+1,0..Nc+1} binary;                        # p' type gray

         var gq{0..Nr+1,0..Nc+1} binary;                        # 'q type gray

         var gb{0..Nr+1,0..Nc+1} binary;                        # b, type gray

         var gd{0..Nr+1,0..Nc+1} binary;                        # ,d type gray

s.t. ALL00{r in 0..Nr+1,c in 0..Nc+1}: b[r,c]+g[r,c]+w[r,c]=1;

s.t. WALL0{r in 0..Nr+1,c in 0..Nc+1:r=0||r=Nr+1||c=0||c=Nc+1}: b[r,c]=1;

s.t. INI3{r in 1..Nr,c in 1..Nc:ini[r,c] =8}: b[r,c]=0;

## ------------ gray rules -----------------------------

         var indx{1..Nr,1..Nc} >=1,<=5;

s.t. GRAY0{r in 1..Nr,c in 1..Nc:ini[r,c]<=4}: g[r-1,c]+g[r,c+1]+g[r+1,c]+g[r,c-1]=ini[r,c];

s.t. GRAY2{r in 1..Nr,c in 1..Nc:ini[r,c] =8}: g[r,c]=gp[r,c]+gq[r,c]+gb[r,c]+gd[r,c];

s.t. INDEX{r in 1..Nr,c in 1..Nc}: indx[r,c]= 1+gd[r,c]+2*gb[r,c]+3*gp[r,c]+4*gq[r,c];     # indx: for dump

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

s.t. BLCK0{r in 1..Nr,c in 1..Nc:ini[r,c]<=5}: b[r,c]=1;

## ------------ arrows for constructing a diamond -----------------------------

s.t. P00{r in 1..Nr,c in 1..Nc}: gp[r,c-1]<=0.5*(gp[r-1,c]+w[r,c])+gq[r,c];                                   # p

s.t. Q00{r in 1..Nr,c in 1..Nc}: gq[r-1,c-1]<=0.5*(gq[r,c]+w[r,c-1])+gd[r,c-1];                               # q

s.t. D00{r in 1..Nr,c in 1..Nc}: gd[r-1,c]<=0.5*(gd[r,c-1]+w[r-1,c-1])+gb[r-1,c-1];                           # d

s.t. B00{r in 1..Nr,c in 1..Nc}: gb[r,c]<=0.5*(gb[r-1,c-1]+w[r-1,c])+gp[r-1,c];                               # b

## ------------ arrows for constructing a rectangle -----------------------------

s.t. BW00{r in 1..Nr+1,c in 1..Nc+1}: b[r-1,c-1]+gb[r-1,c-1]+gd[r-1,c-1]+w[r,c-1]<=                           # bb -->

         1+0.5*(b[r-1,c]+gb[r-1,c]+gd[r-1,c]+w[r,c])+(b[r,c]+gb[r,c]+gp[r,c]);                               # ww

s.t. BW01{r in 1..Nr+1,c in 1..Nc+1}: w[r-1,c-1]+b[r-1,c]+gb[r-1,c]+gp[r-1,c]<=                               #        wb v

         1+0.5*(w[r,c-1]+b[r,c]+gb[r,c]+gp[r,c])+(b[r,c-1]+gp[r,c-1]+gq[r,c-1]);                             #        wb v

s.t. BW02{r in 1..Nr+1,c in 1..Nc+1}: w[r-1,c]+b[r,c]+gp[r,c]+gq[r,c]<=                                       # <-- ww

         1+0.5*(w[r-1,c-1]+b[r,c-1]+gp[r,c-1]+gq[r,c-1])+(b[r-1,c-1]+gq[r-1,c-1]+gd[r-1,c-1]);               #     bb

s.t. BW03{r in 1..Nr+1,c in 1..Nc+1}: b[r,c-1]+gq[r,c-1]+gd[r,c-1]+w[r,c]<=                                   # bw  A

         1+0.5*(b[r-1,c-1]+gq[r-1,c-1]+gd[r-1,c-1]+w[r-1,c])+(b[r-1,c]+gd[r-1,c]+gb[r-1,c]);                 # bw  A

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

s.t. BE0001{r in 1..Nr+0,c in 1..Nc+0}: b[r,c-1]+gd[r,c-1]+gq[r,c-1]<=0.5*(1-gq[r,c]+1-gd[r,c]);     # Bx,dx,qx

s.t. BE0002{r in 1..Nr+0,c in 1..Nc+0}: b[r,c+1]+gb[r,c+1]+gp[r,c+1]<=0.5*(1-gp[r,c]+1-gb[r,c]);     # xB,xb,xp

s.t. BE0003{r in 1..Nr+0,c in 1..Nc+0}:                                                                       # B b d

                                              b[r-1,c]+gb[r-1,c]+gd[r-1,c]<=0.5*(1-gb[r,c]+1-gd[r,c]);         # y,y,y

s.t. BE0004{r in 1..Nr+0,c in 1..Nc+0}:                                                                       # y y y

                                              b[r+1,c]+gp[r+1,c]+gq[r+1,c]<=0.5*(1-gp[r,c]+1-gq[r,c]);         # B,p,q

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

         var obj_value;

s.t. minv: obj_value=sum{r in 1..Nr-0, c in 1..Nc-0} g[r,c];

 

maximize mmm: obj_value;

solve;

 

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

for {r in 1..Nr+0}{ 

  for{c in 1..Nc+0}{ printf"%s",if ini[r,c]=8 then"."else "B";

                     printf"%s",if ini[r,c]=8 then "." else ini[r,c];

         } printf("\n");

} printf("\n");

/*

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

for {r in 1..Nr+0}{ 

  for{c in 1..Nc+0}{       printf"%s",if b[r,c] then"BB"else substr("===/Y=P/Yq",2*indx[r,c]-1,2);

         } printf("\n");

  for{c in 1..Nc+0}{       printf"%s",if b[r,c] then"BB"else substr("==/dbY/==Y",2*indx[r,c]-1,2);

         } printf("\n");

} printf("\n");

/* */

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

for {r in 1..Nr+0}{ 

  for{c in 1..Nc+0}{       printf"%s",if b[r,c] then"BB"else substr("===/\=P/\q",2*indx[r,c]-1,2);

         } printf("\n");

  for{c in 1..Nc+0}{       printf"%s",if b[r,c] then"BB"else substr("==/db\/==\",2*indx[r,c]-1,2);

         } printf("\n");

} printf("\n");

/* */

end;

 

 

[問題定義コード例]

“8”は、空白の代用。”5”は、文字なし黒の代用。

 

#p01.txt

data;

                param Nr:=10;

                param Nc:=10;

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

                1  2 8 8 8 8 3 8 8 2 5

                2  8 8 8 8 8 8 8 8 8 2

                3  8 8 4 8 8 8 8 8 8 8

                4  2 5 8 8 8 4 8 8 8 8

                5  8 8 8 8 5 8 8 8 8 2

                6  8 8 8 8 8 8 8 5 5 5

                7  8 5 8 8 8 5 8 8 8 8

                8  8 2 8 8 4 8 8 5 8 8

                9  8 8 5 8 8 8 8 8 8 8

                10 8 8 2 8 8 3 8 8 5 1;

end;

 

 

#p02.txt

data;

                param Nr:=10;

                param Nc:=10;

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

                1  8 8 2 8 8 3 8 8 8 8

                2  8 8 5 8 8 8 8 8 8 8

                3  3 8 8 5 8 8 8 5 5 2

                4  8 8 8 8 4 8 8 8 8 8

                5  8 8 8 8 8 5 2 8 8 8

                6  3 8 8 8 8 5 8 8 5 5

                7  8 8 8 8 4 8 8 8 5 1

                8  8 8 8 4 8 8 8 8 8 8

                9  8 8 8 8 8 8 8 8 8 8

                10 5 8 8 8 2 5 8 8 8 2

;end;

 

 

トップページへ

 

Ads by TOK2