GLPKでの波及効果パズルの攻略法(解法)

キューブ王

「波及効果」パズルの求解コードを、GLPKMathProg言語で記述してみた。「波及効果」パズル、ラテン方陣や数独の親戚である。数独的な制約条件付きで、数字をマスに割り振るもの。従って、MathProgで容易に記述できる。

 

[概要]

この「波及効果」、ニコリのパズルである。ニコリのページから「導入部やルール」を、ほぼ抜粋しておく。

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

数字が全部入ったときの達成感を、あなたもぜひ味わってください。

ルール

(1)   太線で区切られた部屋のすべてのマスに、1からその部屋のマス数までの数字を1つずつ入れます。

(2)   同じ数字を、タテまたはヨコの同じ列に入れる場合は、数字と数字のあいだに、数字と同じ数以上の他の数字がなければいけません。例えば、3をふたつ同列に入れる場合は、そのあいだに3マス以上他の数字が入っていなければならないということです。

どんなパズル?

「パズル通信ニコリの長寿コーナー「オモロパズルのできるまで」からは、ニコリオリジナルのいくつもの新作パズルが開発され、一人立ちしているが、この「波及効果」もそのなかのひとつだ。

複雑に構成された「部屋」のコンビネーションが生み出す多様な解き筋がなんとも楽しい。ひとつの数字がとんでもないところに思わぬ「波及効果」を招くという意外性も、このパズルの大きな魅力だろう。

まずは1マスの部屋に1を書きこもう。その隣りに2マスの部屋があったら、その部屋も数字が確定する。

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

 なお、「波及効果」の英語はripple effectだそうである。Rippleは「さざなみ」である。波及効果の英訳が、ripple effectはちょっと違う気がする。というか、「波及効果」という日本語がちょっと違う気がする。

 

[問題の記述、データ構造]

 この問題、ラテン方陣や数独の親戚である。非常に素直に、GLPKMtahProg言語で記述できる。以下の図を考える。

 

 

マスを領域分けする必要がある。第1領域、第2領域、、第22領域(左図)。また、いくつかのマスに数字を配置する必要がある(中図)。以上で問題の定義が終わる。

解答は右図のようになる。個別の領域毎に、数字を1,2,…,Nと置いていく。2.1節に示したルールに従うように置いていく。数独やラテン方陣に親戚のルールである。それだけのことである。

 特別な注意は不要。

 

[解法コード]

 そこでいきなり、解法コード

 

# +++++++++++ ripple effect +++++++++++++++++++++++++++++

              param Nr integer;                                 # number of rows

              param Nc integer;                                 # number of columns

              param N  integer;                                # number of regions

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

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

              param M:=8;                                                      # max area

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

              var area{1..N} >=0;                               # area of regions

              var ban{1..Nr,1..Nc} >=0, <=M;                             # answer board

              var bbb{1..Nr,1..Nc,1..N} binary;            # work board

s.t. INI0{r in 1..Nr,c in 1..Nc:ini2[r,c]>=1}: ban[r,c]=ini2[r,c];

s.t. UNIQ{r in 1..Nr,c in 1..Nc}: sum{n in 1..M} bbb[r,c,n] =1;

s.t. AREA{n in 1..N}: area[n]=sum{r in 1..Nr,c in 1..Nc: ini1[r,c]=n} 1;

 

param Nr,Ncは盤面の行数と列数。Nは領域の数。

Param配列ini1[,]は、上の左図の情報を得るもの。つまり領域分けの情報を得るもの。

Param配列ini2[,]は、上の中図の情報をえるもの。つまり予め設定されているマス内の数字をえるもの。

Param Mは、領域の最大マス数。この問題の場合、5がいいのだが、それより大きい8でも構わない。

変数area[]は、個別領域のマス数(面積)を格納するもの。実質は定数なのだがparamで設定するやり方が分からない(orできない)ので、変数にしてある。

変数ban[,]は、答えをいれる盤面。個別の要素(マス)に数字が入る。

変数bbb[,,]は、ban[,]の3次元版。Binaryである。Ban[r,c]=n/!=nßàbbb[r,c,n]=1/0

制約INI0は、予め指定してあるマス[r,c]内の数字ini2[r,c]ban[r,c]に移すもの。制約でなく、代入(or定数化)

制約UNIQは、個別のマスban[r,c]に1つ数字が入ることを示すもの。

制約AREAは、個別の領域n(ini1[r,c]=n)のマス数を数え、それをarea[n]にしまうもの。制約でなく代入。

 

## ---------- effect ----------------------------

s.t. CONV{r in 1..Nr,c in 1..Nc}: sum{n in 1..M} n*bbb[r,c,n] =ban[r,c];

s.t. EF00{r in 1..Nr,c in 1..Nc,n in 1..N:ini1[r,c]=n}: ban[r,c]<=area[n];

s.t. EF01{n in 1..N,m in 1..M}:

                             sum{r in 1..Nr,c in 1..Nc: n=ini1[r,c]} bbb[r,c,m] <=1;

#s.t. EF02{r in 1..Nr,c in 1..Nc,m in 1..M: m=ini2[r,c]}:

#             sum{ n in 1..m:r+n<=Nr}bbb[r+n,c,m]

#             +sum{ n in 1..m:r-n>=1} bbb[r-n,c,m]

#             +sum{ n in 1..m:c+n<=Nc}bbb[r,c+n,m]

#             +sum{ n in 1..m:c-n>=1} bbb[r,c-n,m]     =0;

s.t. EF03{r in 1..Nr,c in 1..Nc,m in 1..M}:

               sum{ n in 1..m:r+n<=Nr}bbb[r+n,c,m]

              +sum{ n in 1..m:r-n>=1} bbb[r-n,c,m]

              +sum{ n in 1..m:c+n<=Nc}bbb[r,c+n,m]

              +sum{ n in 1..m:c-n>=1} bbb[r,c-n,m]     <=100*(1-bbb[r,c,m]);

 

制約CONVは、ban[r,c]=nbbb[r,c,n]との相互の変換。

制約EF00は、領域n内に1..area[n]の数字を入れるもの。

制約EF01は、領域n内の個別の数字mは重複しないことを示すもの。制約EF00,EF01でルール(1)に対応。

制約EF02はコメント化してあるが説明しておく。数字mが予め指定してあったマスでの場合であるが、縦横のm近傍に、同じ数字があってはならないというもの。ルール(2)に対応。

制約EF03は、制約EF02に似ている。Ban[r,c]=mであれば、bbb[r,c,m]=1であり、右辺は0となる。従って左辺も0となる、というもの。丁度ルール(2)に対応。

 

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

maximize MMM: sum{r in 1..Nr,c in 1..Nc}ban[r,c];

#minimize MMM: sum{r in 1..Nr,c in 1..Nc}ban[r,c];

solve;

 

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

for {r in 1..Nr}{ 

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

}

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

for {r in 1..Nr}{ 

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

}

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

for{n in 1..N}{ printf"%2.0f ",area[n];} printf("\n");

 

printf "--ban-----\n";

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

 

  printf"|%2.0f ",ban[1,1];

  for{c in 2..Nc}{

              printf if ini1[1,c-1]-ini1[1,c] then "|" else " ";

              printf"%2.0f ",ban[1,c];

  }          printf"|\n";

for{r in 2..Nr}{ 

  printf"+";

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

  } printf"\n";

  printf"|%2.0f ",ban[r,1];

  for{c in 2..Nc}{

              printf if ini1[r,c-1]-ini1[r,c] then "|" else " ";

              printf"%2.0f ",ban[r,c];

  }          printf"|\n";

}

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

end;

 

最後は、solvedumpDumpが長い。なぜかというと、解答部分を親切に表示したからである。ダンプ結果を示す。細かい説明はしない。

 

[波及効果とMathProg]

波及効果、MathProgで簡単に記述できると思っていた。実際に、非常に素直に、簡単に記述できた。10*10程度の問題であれば、普通のPCで求解時間0.1secなどと表示される。求解時間は問題とならない。MathProgとの相性は極端にいい。

問題の定義に辟易し、特に領域分けに辟易し、4つしか解いてない。この4つの結果を示しておく。

 

問題

p1 8*8

p2 8*8

p3 10*10

p4 10*10

 

時間sec

0.0

0.0

0.1

0.2

3GHz

容量MB

1.3

1.3

2.2

2.4

512KBキャッシュ

 

なお、p3,p4は表示した答えが正しいかどうか調べてない。出題ページでの答えの取得法がわからなかったもので。

 

 

 [MathProg求解コード]

 

# +++++++++++ ripple effect +++++++++++++++++++++++++++++

              param Nr integer;                                 # number of rows

              param Nc integer;                                 # number of columns

              param N  integer;                                # number of regions

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

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

              param M:=8;                                                      # max area

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

              var area{1..N} >=0;                               # area of regions

              var ban{1..Nr,1..Nc} >=0, <=M;                             # answer board

              var bbb{1..Nr,1..Nc,1..N} binary;            # work board

s.t. INI0{r in 1..Nr,c in 1..Nc:ini2[r,c]>=1}: ban[r,c]=ini2[r,c];

s.t. UNIQ{r in 1..Nr,c in 1..Nc}: sum{n in 1..M} bbb[r,c,n] =1;

s.t. AREA{n in 1..N}: area[n]=sum{r in 1..Nr,c in 1..Nc: ini1[r,c]=n} 1;

## ---------- effect ----------------------------

s.t. CONV{r in 1..Nr,c in 1..Nc}: sum{n in 1..M} n*bbb[r,c,n] =ban[r,c];

s.t. EF00{r in 1..Nr,c in 1..Nc,n in 1..N:ini1[r,c]=n}: ban[r,c]<=area[n];

s.t. EF01{n in 1..N,m in 1..M}:

                             sum{r in 1..Nr,c in 1..Nc: n=ini1[r,c]} bbb[r,c,m] <=1;

#s.t. EF02{r in 1..Nr,c in 1..Nc,m in 1..M: m=ini2[r,c]}:

#             sum{ n in 1..m:r+n<=Nr}bbb[r+n,c,m]

#             +sum{ n in 1..m:r-n>=1} bbb[r-n,c,m]

#             +sum{ n in 1..m:c+n<=Nc}bbb[r,c+n,m]

#             +sum{ n in 1..m:c-n>=1} bbb[r,c-n,m]     =0;

s.t. EF03{r in 1..Nr,c in 1..Nc,m in 1..M}:

               sum{ n in 1..m:r+n<=Nr}bbb[r+n,c,m]

              +sum{ n in 1..m:r-n>=1} bbb[r-n,c,m]

              +sum{ n in 1..m:c+n<=Nc}bbb[r,c+n,m]

              +sum{ n in 1..m:c-n>=1} bbb[r,c-n,m]     <=100*(1-bbb[r,c,m]);

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

maximize MMM: sum{r in 1..Nr,c in 1..Nc}ban[r,c];

#minimize MMM: sum{r in 1..Nr,c in 1..Nc}ban[r,c];

solve;

 

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

for {r in 1..Nr}{ 

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

}

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

for {r in 1..Nr}{ 

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

}

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

for{n in 1..N}{ printf"%2.0f ",area[n];} printf("\n");

 

printf "--ban-----\n";

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

 

  printf"|%2.0f ",ban[1,1];

  for{c in 2..Nc}{

              printf if ini1[1,c-1]-ini1[1,c] then "|" else " ";

              printf"%2.0f ",ban[1,c];

  }          printf"|\n";

for{r in 2..Nr}{ 

  printf"+";

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

  } printf"\n";

  printf"|%2.0f ",ban[r,1];

  for{c in 2..Nc}{

              printf if ini1[r,c-1]-ini1[r,c] then "|" else " ";

              printf"%2.0f ",ban[r,c];

  }          printf"|\n";

}

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

end;

 

 

[問題定義コード]

 

どこかでサーチした問題を2つ載せておく。

 

## p03.txt


data;   ## ---------- input --------------

param Nr:= 10;

param Nc:= 10;

param N:= 29;

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

        1       1  2  3  4  5  6  7  8  8  8

        2       1  2  3  4  5  6  7  9  9  8

        3      10  2  3  4  5  6  7  9 12 12

        4      10 11  3  4  5  6  7  9 12 12

        5      10 13 13  4  5  6  7  9 18 18

        6      13 13 14 15 16 16 17 18 18 18

        7      19 19 19 15 21 16 22 22 22 23

        8      19 20 20 15 21 21 22 22 22 29

        9      19 19 24 15 21 21 21 27 28 29

        10     24 24 24 25 26 26 21 27 28 29

;

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

        1       1  2  3  4  5  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

        7       5  6  0  0  0  0  0  0  0  0

        8       0  0  0  0  0  0  0  0  0  0

        9       0  0  0  0  0  0  0  0  0  0

        10      0  0  0  0  0  0  0  0  0  0

;end;

 

##p04.txt

data;   ## ---------- input --------------

param Nr:= 10;

param Nc:= 10;

param N:= 26;

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

        1       1  2  3  3  3  3  3  4  4  4

        2       1  2  5  5  6  7  7  7  8  9

        3      10  2  5  5 11 11 12 12  8  9

        4      10  2  5  5 11 11 12 12  8  9

        5      10  2 13 13 11 14 14 14  8  9

        6      10 15 13 13 13 17 14 14 19  9

        7      10 15 16 16 17 17 18 18 19 20

        8      10 15 16 16 17 17 18 18 19 26

        9      21 15 22 22 22 23 18 18 19 26

        10     21 24 24 24 24 24 25 25 19 26

;

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

        1       0  0  4  0  0  0  0  0  0  1

        2       0  0  0  0  0  0  0  0  0  0

        3       0  0  0  4  0  0  0  0  0  0

        4       0  0  2  0  0  0  0  0  0  0

        5       0  0  0  0  0  0  0  3  0  0

        6       0  0  4  0  0  0  0  0  0  0

        7       0  0  0  0  0  0  0  1  0  0

        8       0  0  0  0  0  0  3  0  0  0

        9       0  0  0  0  0  0  0  0  0  0

        10      2  0  0  0  0  0  0  1  0  0

;end;

 

 

トップページへ

 

 

Ads by TOK2