整数計画法によるパズル解法 のりのり

キューブ王 海永

「のりのり」パズルの求解コードを、GLPKMathProg言語で記述してみた。「のりのり」、あるルールに従い盤面内のマスに黒石を置いていくもの。

パズルのルールは極端に簡単である。パズル自体も簡単なものに属するといえよう。整数計画法での解法も、極端に簡単である。

 

[導入]

以下は「のりのり」の問題例()と解答例()を示している。

 

 

以下も問題例と解答例だが、ここでの約束に従うもの。なお、GDは黒石のつもりである。

 

 

「のりのり」はwikipediaで説明されてないので、パズル本の記載内容にしたがいルールを説明しておく。

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

盤面のいくつかのマスを黒くぬります。

(1)   黒マスは必ず、タテかヨコに丁度2つだけつながったカタマリになります。

(2)   線で区切られた各部分(部屋)には、黒マスが2つずつ入ります。

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

 

[解法コード]

解法コードの基本部は以下。

 

## ++++++++++ laver +++++++++++++++++++++++++++++

        param Nr integer;                               # number of rows

        param Nc integer;                               # number of columns

        param N  integer;                               # number of regions

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

## ---------- laver -----------------------------

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

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

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

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

s.t. Cpair2{r in 1..Nr,c in 1..Nc}: 3*b[r,c]<=(1-b[r-1,c])+(1-b[r,c+1])+(1-b[r+1,c])+(1-b[r,c-1]);

 

Param Nr,Ncは盤面の行数と列数。

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

Param ini1は、問題定義用の2次元配列。N個の部屋毎に、部屋の識別番号を指定。

Var bは、黒マスかどうかを示す。

制約Cwallは、本来の盤面より外のマスは黒マスではない、というもの。

制約C2seatは、個別の部屋に2つの黒マスが置かれる、というもの。

制約Cpair1は、着目マスが黒なら、隣接4マスの内の1つ以上が黒マスである、というもの。

制約Cpari2は、着目マスが黒なら、離接4マスの内の3つ以上が白マスである、というもの。

 

以上でいい。別にダンプ用のコードが必要だが、それについては省略。勿論、[求解コード」節には載せてある。

 

[速度など]

 ニコリの「のりのり1」の10*10問題や14*24問題を7個解いてみた。以下の結果となった。

 

 

のりのりは、極端に簡単なパズルということだろう。14*24問題が、0.3sec以内、1.1MB以下である。

 

[MathProg求解コード]

 

## ++++++++++ laver +++++++++++++++++++++++++++++

        param Nr integer;                               # number of rows

        param Nc integer;                               # number of columns

        param N  integer;                               # number of regions

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

## ---------- laver -----------------------------

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

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

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

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

s.t. Cpair2{r in 1..Nr,c in 1..Nc}: 3*b[r,c]<=(1-b[r-1,c])+(1-b[r,c+1])+(1-b[r+1,c])+(1-b[r,c-1]);

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

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

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

solve;

printf "--problem-----\n";

for{r in 1..Nr}{

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

  for{c in 1..Nc}{

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

        printf "  ";

  } printf "|\n";

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

 

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

for{r in 1..Nr}{

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

  for{c in 1..Nc}{

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

        printf if b[r,c] then "GD" else "  ";

#       printf if b[r,c] then "@ " else "  ";

  } printf "|\n";

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

end;

 

 

[問題定義コード]

 

#p01.txt

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

param Nr:= 10;

param Nc:= 10;

param N:= 23;

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

        1    1  2  2  3  3  3  3  3  4  5

        2    1  2  2  3  3  3  6  6  4  5

        3    7  7  7  3  8  9  6  6  4 10

        4   11  7 12  8  8  9  9  9  4 10

        5   11 11 12 12  8  9  9  9 10 10

        6   11 13 13 13 14 14 14 15 15 10

        7   16 16 13 13 17 14 14 15 15 15

        8   16 16 17 17 17 17 18 18 19 19

        9   16 16 20 20 17 17 18 18 18 19

        10  21 21 20 22 22 22 18 18 23 23

;end;

 

 

#p79.txt

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

param Nr:= 14;

param Nc:= 24;

param N:= 62;

param ini1: 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24:=

        1   1  1  1  1  1  2  2  2  2  2  3  3  3  4  4  4  5  5  5  6  6  6  6  6

        2   1  1  7  7  8  8  9  9 10  2 11 11 11 11 11 11 11 11 11  6  6 12 13  6

        3  14 14 15 15  8  8  9  9 10  2 16 16 16 16 16 16 16 16 16 17 17 12 13  6

        4  14 14 15 15  8  8  8  8  8  2 16 21 21 21 21 22 23 23 17 17 24 12  6  6

        5  18 18 18 18 18 19 19 19 19 20 16 21 21 25 22 22 23 23 17 26 24 12  6  6

        6  27 27 28 28 29 29 29 30 30 20 31 31 31 25 22 32 32 32 26 26 24 24 33 34

        7  27 27 28 28 29 29 29 30 30 20 31 31 31 25 22 32 32 32 35 26 24 24 33 34

        8  27 27 28 28 36 36 37 37 30 20 38 38 31 31 22 22 32 32 35 35 35 33 33 34

        9  27 27 39 39 36 40 37 37 30 20 41 38 38 38 22 42 32 32 32 35 35 43 43 34

        10 44 44 44 44 44 40 40 40 30 20 41 41 45 45 42 42 42 32 32 46 34 34 34 34

        11 44 44 44 47 44 40 48 48 30 20 49 41 45 54 50 50 42 46 46 46 34 34 34 34

        12 51 51 47 47 52 40 53 53 30 20 49 49 45 54 55 55 55 56 56 56 56 57 57 57

        13 58 58 47 47 52 52 53 53 30 20 20 20 20 54 55 55 59 59 59 59 56 56 56 60

        14 58 58 47 47 52 61 61 61 61 54 54 54 54 54 54 54 62 62 56 56 56 56 56 60

;end;

 

 

トップページへ

 

Ads by TOK2