整数計画法によるパズル解法 橋をかけろ

キューブ王

「橋をかけろ」パズルの求解コードを、GLPKMathProg言語で記述してみた。「橋をかけろ」、島とみなした○印の間を線で結んでいくパズルである。

以下は「橋をかけろ」の問題例()と解答例()を示している。ニコリのお試し問題から。なお、右は9*9問題ということを納得するために、空き部分にも○をおいたもの。

 

 

まず、wikipediaにほぼ従い、ルールや解法を説明しておく。

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

橋をかけろは、数字同士を線でつなぐペンシルパズルである。英語ではBridgesと呼ばれる。

[ルール]

(1)     島同士を線(橋)で結び、すべての数字が線でつながっているようにする。

(2)     線は他の線と交差したり数字を横切ったりしない。

(3)     線は水平方向か垂直方向に引かれる。

(4)     どの数の間にも2本までしか線は引けない。

(5)     数字はその数字から引かれる線の数を表す。

 

[机上解法]

橋をかけろを解く上で最初の手がかりになるのは、「8の島」、辺上の「6の島」、角の「4の島」である。これらは、線が引ける方向すべてに2本ずつ線を引く。制約上そうなる。

次に、「7の島」、辺上の「5の島」、角の「3の島」である。これらは、引ける方向に少なくとも1本ずつの線が引ける。なぜなら、その方向に線を引かないと制約を満たせないからである。

1つ以上の線が確定すると、それによって他の数字から引かれる線が確定したり、別の数字から線を延ばせる方向が制限されたりして新たな手がかりが発生する。

 

すべての数字が一つながりになるというルールから、すべての数字から線が引かれ、かつ、他の数字につながっていない「閉じた」グループが存在しないように線を引いていく必要がある。最も簡単な例としては、1同士の間に線が引かれることはない。

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

 

[データ構造]

 「かける橋」、いくつかの形式があるようである。しかし、このパズルの場合、「架ける橋」と思うのが正解だろう。島がない部分にも橋脚は設置でき、橋脚間に橋桁を架けていく。1単位以上の長い橋も構築できる。そういう想定で求解コードを記述できる。

 

 

左の図は、島と橋脚を示したもの。”1,2””1,3”などは、島と橋脚の座標である。島には”1””5”などの数字が指定されている。

右の図は、架けられた橋桁(赤い長四角)を示したもの。”1,3””1,4”などは、橋桁の座標である。

 

この「橋をかけろ」パズル、ルール(1)の後半部「すべての数字が線でつながっているようにする」以外は、素直に解法を記述できる。ルール(1)の後半部にサボり解法を適用すれば、全体コードを容易に記述できることになる。精密解法は、島間に木構造を導入し、島数を数えあげていけばいい。

ここでは、サボり解法と精密解法の2つを提示することにする。

 

 [サボり解法]

 左の図を問題定義入力とし、右の図を解答とする。お試し問題の最初の問題。

 

## ++++++++++ Bridges +++++++++++++++++++++++++++++

                              param Nr integer;                                                                        # number of rows

                              param Nc integer;                                                                        # number of columns

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

                              param W:=1;               # 1,2,0.5                                                   # a parameter of the objective function

 

param Nrは問題の行数、param Ncは問題の列数。

Param ini1は問題定義の配列。上の左の図参照。図で”.”と表示されている部分は、実際の定義では”0”と指定。”0”は「橋脚のみ」を示し、正整数は島を示す。

Param Wは、サボり解法に関わるパラメータ。最大化させる式の計算法を単に調整するだけ。これは後で説明する。

 

## ---------- Bridges -----------------------------

                            var bh1{1..Nr+1,1..Nc+1} binary;                   # 1/0: 1st

                            var bh2{1..Nr+1,1..Nc+1} binary;                   # 1/0: 2nd

                            var bv1{1..Nr+1,1..Nc+1} binary;                   # 1/0: 1st

                            var bv2{1..Nr+1,1..Nc+1} binary;                   # 1/0: 2nd

                            var bhv{1..Nr,1..Nc} integer;

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

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

s.t. SCNDh{r in 1..Nr+1,c in 1..Nc+1}: bh2[r,c]<=bh1[r,c];

s.t. SCNDv{r in 1..Nr+1,c in 1..Nc+1}: bv2[r,c]<=bv1[r,c];

s.t. ISLAND{r in 1..Nr,c in 1..Nc:ini1[r,c]!=0}:

                            bh1[r,c]+bh2[r,c]+bv1[r,c]+bv2[r,c]+

                            bh1[r,c+1]+bh2[r,c+1]+bv1[r+1,c]+bv2[r+1,c]=abs(ini1[r,c]);

s.t. SEA0{r in 1..Nr,c in 1..Nc:ini1[r,c]=0}: bh1[r,c]+bv1[r,c]<=1;

s.t. SEAh{r in 1..Nr,c in 1..Nc:ini1[r,c]=0}:

                            bh1[r,c]+bh2[r,c]=bh1[r,c+1]+bh2[r,c+1];

s.t. SEAv{r in 1..Nr,c in 1..Nc:ini1[r,c]=0}:

                            bv1[r,c]+bv2[r,c]=bv1[r+1,c]+bv2[r+1,c];

s.t. SEAhv{r in 1..Nr,c in 1..Nc}: bhv[r,c]=1+bh1[r,c]+bh2[r,c]+3*(bv1[r,c]+bv2[r,c]);

 

変数bh1[,],bh2[,]は、上の図の横に長い赤四角に対応する。1/0で橋桁の有/無を表す。Bh1[,]は1本目、bh2[,]は2本目に対応。

変数bv1[,],b2v[,]も同様。勿論、縦に長い赤四角に対応する。  変数bhv[,]は制約SEAhv参照。

制約WALLhは、左端の島や橋脚から左方向に橋桁が置かれるはずはない、同様に右端の島や橋脚から右方向に橋脚が置かれるはずはない、というもの。

制約WALLvは、制約WALLhに同様。勿論、水平方向でなく、垂直方向。

制約SCNDhは、第一橋桁が架かってなければ、第2橋桁は架かってない、というもの。水平方向。

制約SCNDvは、制約SCNDhと同様。垂直方向。

制約ISLANDは、その島から伸びている橋桁の数を指定。ルール(5)に対応。

制約SEA0は、(島でない)橋脚のみの場合、水平方向と垂直方向の橋桁が架かってはならないというもの。ルール(2)の前半部に対応。

制約SEAhは、(島でない)橋脚のみの場合、右側と東側の橋脚数が同じというもの。ルール(1)の前半部に対応。勿論水平方向。

制約SEAvは、(島でない)橋脚のみの場合、上側と下側の橋脚数が同じというもの。ルール(1)の前半部に対応。勿論垂直方向。

制約SEAhvは、解答ダンプ用。実際上は制約でなく代入。 文字列" -=|..H"の特定の1文字を指す。

”-“は水平方向橋桁1つ。”=”は水平方向橋桁2つ。”|”は垂直方向橋桁1つ。”H”は垂直方向橋桁2つ。

 以上で、制約の記述はおしまい。

 

maximize MMM: sum{r in 1..Nr,c in 1..Nc}(W*bh1[r,c]+bv1[r,c]);

solve;

 

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

for {r in 1..Nr}{ 

  printf"\n";

  for{c in 1..Nc}{ printf"  %s",if ini1[r,c]then ini1[r,c]else".";} printf("\n");

} printf("\n");

 

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

for {r in 1..Nr}{ 

  for{c in 1..Nc}{ printf"  %s",substr(" |H",bv1[r,c]+bv2[r,c]+1,1);} printf(" \n");

  for{c in 1..Nc}{ printf"%s %s",substr(" -=",1+bh1[r,c]+bh2[r,c],1),

                             if ini1[r,c] then abs(ini1[r,c])else substr(" -=|..H",bhv[r,c],1) ;} printf(" \n");

} printf(" \n");

end;

 

 maximaize MMMが、サボり解法そのもの。水平方向の第1橋桁bh1[,]と垂直方向の第1橋桁bv1[,]を数えあげているだけ。Param Wが1の場合、8個の問題で走行実験し、7個正解した。不正解だった問題は、W:=2で正解した。サボり解法、かなり良好である。

 残りのコードは、問題のダンプと答えのダンプ。この節の最初の図の、左側と右側をダンプするもの。詳細は略す。

 

 [サボり解法での速度]

お試し問題の最初の8個で走行実験。以下の結果を得ている。

 

問題

p01 9*9

p02 9*9

p03 9*9

p04 9*16

p05 9*16

p06 9*16

p07 13*22

p08 13*22

時間sec

0.0

0.0

0.0

0.0

0.0

0.0

0.4

0.4

2.2GHz

容量MB

0.7

0.7

0.8

1.2

1.3

1.5

2.8

2.5

i7-2670QM

 

それなりに速いといえよう。W:=2で走行させて、全てに正解した。

 

[精密解法]

 サボり解法、かなり良好であった。が、しかし、任意の問題に正解できる保証はない。やはり精密解法がほしくなった。それで、精密解法も書いてみた。

 ルール(1)の後半部「すべての数字が線でつながっているようにする」という部分を精密に記述すればいい。

 

左が問題例。右が解答例である。お試し問題の2番目の問題。解答図中にループが形成される問題を選んだ。真ん中は、右が確かに解答になるかどうかを判断するための木構造である。

左の問題、(右上隅の)1つの数字が負数となっている。この島に島数を数えあげよという意味である。そして中の図の木構造、右上隅に22が数えあげられている。島数22に等しいので、右の図は正解だと判断できる。そういう、やり方でいい。

 コードも少し説明しておく。

 

## ---------- tree -----------------------------

                                var au{0..Nr+1,0..Nc+1} binary;

                                var ad{0..Nr+1,0..Nc+1} binary;

                                var al{0..Nr+1,0..Nc+1} binary;

                                var ar{0..Nr+1,0..Nc+1} binary;

                                var nu{0..Nr+1,0..Nc+1} >=0;

                                var nd{0..Nr+1,0..Nc+1} >=0;

                                var nl{0..Nr+1,0..Nc+1} >=0;

                                var nr{0..Nr+1,0..Nc+1} >=0;

                                var num{1..Nr,1..Nc} >=0;

s.t. ARRw{r in 0..Nr+1,c in 0..Nc+1:r=0||r=Nr+1||c=0||c=Nc+1}: au[r,c]+ad[r,c]+al[r,c]+ar[r,c]=0;

s.t. DIRud{r in 1..Nr,c in 1..Nc}: au[r,c]+ad[r-1,c]<=bv1[r,c];

s.t. DIRlr{r in 1..Nr,c in 1..Nc}: al[r,c]+ar[r,c-1] =bh1[r,c];

 

変数au[,],ad[,],al[,]ar[,]は、中の図の矢印 ”^”, ”v”, ”<” ,”>” に対応する。これらの矢印で木構造を構築していく。

変数 nu[,], nd[,], nl[,], nr[,]は、矢印 ”^”, ”v”, ”<” ,”>”で運ばれる島数を表す。

変数num[,]は、自分と子孫全体の島数を表す。

制約ARRwは、本来の盤面の1つ外では、矢印は存在しないというもの。

制約DIRudは、垂直方向の第一橋桁bv1[r,c]があれば、上向き矢印au[r,c]か下向き矢印ad[r-1,c]がある(場合がある)というもの。不等号”<=”はループを拒否し、木構造を構築するため。

制約DIRlrは、水平方向の第一橋桁bh1[r,c]があれば、左向き矢印al[r,c]か右向き矢印ar[r,c-1]があるというもの。

 

s.t. ARRi0{r in 1..Nr,c in 1..Nc:ini1[r,c]>= 1}: au[r,c]+ad[r,c]+al[r,c]+ar[r,c]=1;

s.t. ARRi2{r in 1..Nr,c in 1..Nc:ini1[r,c]<=-1}: au[r,c]+ad[r,c]+al[r,c]+ar[r,c]=0;

s.t. ARRu{r in 1..Nr,c in 1..Nc:ini1[r,c] =0}: au[r,c]=au[r+1,c];

s.t. ARRd{r in 1..Nr,c in 1..Nc:ini1[r,c] =0}: ad[r,c]=ad[r-1,c];

s.t. ARRl{r in 1..Nr,c in 1..Nc:ini1[r,c] =0}: al[r,c]=al[r,c+1];

s.t. ARRr{r in 1..Nr,c in 1..Nc:ini1[r,c] =0}: ar[r,c]=ar[r,c-1];

 

制約ARRi0は、(通常の)(ini1[r,c]>=1)なら、出ていく矢印が1つということを示す。

制約ARRi2は、島数集約の島(ini1[r,c]<=-1)なら、出ていく矢印は1つもないということを示す。

制約ARRu,d,l,rは、(橋脚だけで)島でない(ini1[r,c]=0)なら、入ってきた矢印と同じ方向の矢印が出ていくことを示す。

 

s.t. NUMu{r in 0..Nr+1,c in 0..Nc+1}: nu[r,c]<=Nr*Nc/2*au[r,c];       # number can be send with an arrow

s.t. NUMd{r in 0..Nr+1,c in 0..Nc+1}: nd[r,c]<=Nr*Nc/2*ad[r,c];       # number can be send with an arrow

s.t. NUMl{r in 0..Nr+1,c in 0..Nc+1}: nl[r,c]<=Nr*Nc/2*al[r,c];          # number can be send with an arrow

s.t. NUMr{r in 0..Nr+1,c in 0..Nc+1}: nr[r,c]<=Nr*Nc/2*ar[r,c];        # number can be send with an arrow

 

制約NUMu,d,l,rは、binary変数au[,],ad[,],al[,]ar[,]が1の場合に限り、運ぶ島数nu[,], nd[,], nl[,], nr[,] が0以外となることを示す。

つまり、矢印 ”^”, ”v”, ”<” ,”>”が島数nu[,], nd[,], nl[,], nr[,]を運ぶことになる。

 

s.t. NUM0{r in 1..Nr,c in 1..Nc:ini1[r,c]!=0}:                                   # recieve numbers from sons

                                num[r,c]= 1+ nu[r+1,c]+nd[r-1,c]+nl[r,c+1]+nr[r,c-1];

s.t. NUM1{r in 1..Nr,c in 1..Nc:ini1[r,c]=0}:                                    # receive numbers from sons

                                num[r,c]=    nu[r+1,c]+nd[r-1,c]+nl[r,c+1]+nr[r,c-1];

s.t. NUM2{r in 1..Nr,c in 1..Nc:ini1[r,c]>=0}:                                  # send number to a father

                                nu[r,c]+nd[r,c]+nl[r,c]+nr[r,c]=num[r,c];

s.t. NUM3{r in 1..Nr,c in 1..Nc:ini1[r,c]<=-1}:                                 # the root does not have a father

                                nu[r,c]+nd[r,c]+nl[r,c]+nr[r,c]=0;

 

制約NUM0は、島であれば、子供たちが運んできた島数に1を加えたものが、自分と子孫たちの島数num[r,c]である、という意味。

制約NUM1は、橋脚だけであれば、子供たちが運んできた島数が、自分と子孫たちの島数num[r,c]である、という意味。

制約NUM2は、集約指定でない(ini1[r,c]>=0)場合、自分と子孫たちの島数num[r,c]を何処かの親1人に全て送るというもの。

制約NUM3は、集約指定(ini1[r,c]<=-1)の島の場合、親がいないので、自分と子孫たちの島数num[r,c]を誰にも送らないというもの。

 

ほかに、最大化制約とダンプのコードが必要だが、その説明は省略する。勿論、[解法コード]節には載せている。

 

[精密解法での速度]

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

 

問題

p01 9*9

p02 9*9

p03 9*9

p04 9*16

p05 9*16

p06 9*16

p07 13*22

p08 13*22

時間sec

0.0

0.0

0.0

0.0

0.1

0.3

1.1

2.6

2.2GHz

容量MB

2.0

1.9

2.1

3.3

3.5

3.8

7.6

6.9

i7-2670QM

 

予想通り『サボり解法』よりも5倍遅いと思われる。しかし、これもかなり速い。13*22問題が解けるとは思っていなかったが、気楽に解けている。

 

[サボり解法コード]

 

## ++++++++++ Bridges +++++++++++++++++++++++++++++

param Nr integer;                                        # number of rows

param Nc integer;                                        # number of columns

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

param W:=1;               # 1,2,0.5                   # a parameter of the objective function

## ---------- Bridges -----------------------------

                                var bh1{1..Nr+1,1..Nc+1} binary;                                                  # 1/0: 1st

                                var bh2{1..Nr+1,1..Nc+1} binary;                                                 # 1/0: 2nd

                                var bv1{1..Nr+1,1..Nc+1} binary;                                                   # 1/0: 1st

                                var bv2{1..Nr+1,1..Nc+1} binary;                                                  # 1/0: 2nd

                                var bhv{1..Nr,1..Nc} integer;

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

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

s.t. SCNDh{r in 1..Nr+1,c in 1..Nc+1}: bh2[r,c]<=bh1[r,c];

s.t. SCNDv{r in 1..Nr+1,c in 1..Nc+1}: bv2[r,c]<=bv1[r,c];

s.t. ISLAND{r in 1..Nr,c in 1..Nc:ini1[r,c]!=0}:

                                bh1[r,c]+bh2[r,c]+bv1[r,c]+bv2[r,c]+

                                bh1[r,c+1]+bh2[r,c+1]+bv1[r+1,c]+bv2[r+1,c]=abs(ini1[r,c]);

s.t. SEA0{r in 1..Nr,c in 1..Nc:ini1[r,c]=0}: bh1[r,c]+bv1[r,c]<=1;

s.t. SEAh{r in 1..Nr,c in 1..Nc:ini1[r,c]=0}:

                                          bh1[r,c]+bh2[r,c]=bh1[r,c+1]+bh2[r,c+1];

s.t. SEAv{r in 1..Nr,c in 1..Nc:ini1[r,c]=0}:

                                           bv1[r,c]+bv2[r,c]=bv1[r+1,c]+bv2[r+1,c];

s.t. SEAhv{r in 1..Nr,c in 1..Nc}: bhv[r,c]=1+bh1[r,c]+bh2[r,c]+3*(bv1[r,c]+bv2[r,c]);

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

maximize MMM: sum{r in 1..Nr,c in 1..Nc}(W*bh1[r,c]+bv1[r,c]);

solve;

 

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

for {r in 1..Nr}{ 

  printf"\n";

  for{c in 1..Nc}{ printf"  %s",if ini1[r,c]then ini1[r,c]else".";} printf("\n");

} printf("\n");

 

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

for {r in 1..Nr}{ 

  for{c in 1..Nc}{ printf"  %s",substr(" |H",bv1[r,c]+bv2[r,c]+1,1);} printf(" \n");

  for{c in 1..Nc}{ printf"%s %s",substr(" -=",1+bh1[r,c]+bh2[r,c],1),

                                                                          if ini1[r,c] then abs(ini1[r,c])else substr(" -=|..H",bhv[r,c],1) ;} printf(" \n");

} printf(" \n");

end;

 

 

[精密解法コード]

## ++++++++++ Bridges +++++++++++++++++++++++++++++

                                param Nr integer;                                                                        # number of rows

                                param Nc integer;                                                                        # number of columns

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

                                param W:=1;               # 1,2,0.5                                                   # a parameter of the objective function

## ---------- Bridges -----------------------------

                                var bh1{1..Nr+1,1..Nc+1} binary;                   # 1/0: 1st

                                var bh2{1..Nr+1,1..Nc+1} binary;                   # 1/0: 2nd

                                var bv1{1..Nr+1,1..Nc+1} binary;                   # 1/0: 1st

                                var bv2{1..Nr+1,1..Nc+1} binary;                   # 1/0: 2nd

                                var bhv{1..Nr,1..Nc} integer;

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

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

s.t. SCNDh{r in 1..Nr+1,c in 1..Nc+1}: bh2[r,c]<=bh1[r,c];

s.t. SCNDv{r in 1..Nr+1,c in 1..Nc+1}: bv2[r,c]<=bv1[r,c];

s.t. ISLAND{r in 1..Nr,c in 1..Nc:ini1[r,c]!=0}:

                                bh1[r,c]+bh2[r,c]+bv1[r,c]+bv2[r,c]+

                                bh1[r,c+1]+bh2[r,c+1]+bv1[r+1,c]+bv2[r+1,c]=abs(ini1[r,c]);

s.t. SEA0{r in 1..Nr,c in 1..Nc:ini1[r,c]=0}: bh1[r,c]+bv1[r,c]<=1;

s.t. SEAh{r in 1..Nr,c in 1..Nc:ini1[r,c]=0}:

                                bh1[r,c]+bh2[r,c]=bh1[r,c+1]+bh2[r,c+1];

s.t. SEAv{r in 1..Nr,c in 1..Nc:ini1[r,c]=0}:

                                bv1[r,c]+bv2[r,c]=bv1[r+1,c]+bv2[r+1,c];

s.t. SEAhv{r in 1..Nr,c in 1..Nc}: bhv[r,c]=1+bh1[r,c]+bh2[r,c]+3*(bv1[r,c]+bv2[r,c]);

## ---------- tree, counting islands -----------------------------

                                var au{0..Nr+1,0..Nc+1} binary;

                                var ad{0..Nr+1,0..Nc+1} binary;

                                var al{0..Nr+1,0..Nc+1} binary;

                                var ar{0..Nr+1,0..Nc+1} binary;

                                var nu{0..Nr+1,0..Nc+1} >=0;

                                var nd{0..Nr+1,0..Nc+1} >=0;

                                var nl{0..Nr+1,0..Nc+1} >=0;

                                var nr{0..Nr+1,0..Nc+1} >=0;

                                var num{1..Nr,1..Nc} >=0;

s.t. ARRw{r in 0..Nr+1,c in 0..Nc+1:r=0||r=Nr+1||c=0||c=Nc+1}: au[r,c]+ad[r,c]+al[r,c]+ar[r,c]=0;

s.t. DIRud{r in 1..Nr,c in 1..Nc}: au[r,c]+ad[r-1,c]<=bv1[r,c];

s.t. DIRlr{r in 1..Nr,c in 1..Nc}: al[r,c]+ar[r,c-1] =bh1[r,c];

s.t. ARRi0{r in 1..Nr,c in 1..Nc:ini1[r,c]>= 1}: au[r,c]+ad[r,c]+al[r,c]+ar[r,c]=1;

s.t. ARRi2{r in 1..Nr,c in 1..Nc:ini1[r,c]<=-1}: au[r,c]+ad[r,c]+al[r,c]+ar[r,c]=0;

 

s.t. ARRu{r in 1..Nr,c in 1..Nc:ini1[r,c] =0}: au[r,c]=au[r+1,c];

s.t. ARRd{r in 1..Nr,c in 1..Nc:ini1[r,c] =0}: ad[r,c]=ad[r-1,c];

s.t. ARRl{r in 1..Nr,c in 1..Nc:ini1[r,c] =0}: al[r,c]=al[r,c+1];

s.t. ARRr{r in 1..Nr,c in 1..Nc:ini1[r,c] =0}: ar[r,c]=ar[r,c-1];

 

s.t. NUMu{r in 0..Nr+1,c in 0..Nc+1}: nu[r,c]<=Nr*Nc/2*au[r,c];       # number can be send with an arrow

s.t. NUMd{r in 0..Nr+1,c in 0..Nc+1}: nd[r,c]<=Nr*Nc/2*ad[r,c];       # number can be send with an arrow

s.t. NUMl{r in 0..Nr+1,c in 0..Nc+1}: nl[r,c]<=Nr*Nc/2*al[r,c];          # number can be send with an arrow

s.t. NUMr{r in 0..Nr+1,c in 0..Nc+1}: nr[r,c]<=Nr*Nc/2*ar[r,c];        # number can be send with an arrow

 

s.t. NUM0{r in 1..Nr,c in 1..Nc:ini1[r,c]!=0}:                                   # recieve numbers from sons

                                num[r,c]= 1+ nu[r+1,c]+nd[r-1,c]+nl[r,c+1]+nr[r,c-1];

s.t. NUM1{r in 1..Nr,c in 1..Nc:ini1[r,c]=0}:                                    # receive numbers from sons

                                num[r,c]=    nu[r+1,c]+nd[r-1,c]+nl[r,c+1]+nr[r,c-1];

s.t. NUM2{r in 1..Nr,c in 1..Nc:ini1[r,c]>=0}:                                  # send number to a father

                                nu[r,c]+nd[r,c]+nl[r,c]+nr[r,c]=num[r,c];

s.t. NUM3{r in 1..Nr,c in 1..Nc:ini1[r,c]<=-1}:                                 # the root does not have a father

                                nu[r,c]+nd[r,c]+nl[r,c]+nr[r,c]=0;

/* */

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

                                var maxnum>=0;                                                                                                          # number of islands

s.t. GOAL0:maxnum=sum{r in 1..Nr,c in 1..Nc:ini1[r,c]!=0} 1;

s.t. GOAL1{r in 1..Nr,c in 1..Nc:ini1[r,c]<=-1}: maxnum=num[r,c];

maximize MMM: sum{r in 1..Nr,c in 1..Nc}(au[r,c]+ad[r,c]+al[r,c]+ar[r,c]);

solve;

 

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

for {r in 1..Nr}{ 

  printf"\n";

  for{c in 1..Nc}{ printf"  %s",if ini1[r,c]then ini1[r,c]else".";} printf("\n");

} printf("\n");

 

printf"--tree-- maxnum=%3.0f\n",maxnum;

for {r in 1..Nr}{ 

  for{c in 1..Nc}{ printf"  %s",if au[r,c]then"^"else if ad[r-1,c]then"v"else" ";} printf(" \n");

  for{c in 1..Nc}{ printf"%s%2.0f",if al[r,c]then"<"else if ar[r,c-1]then ">"else" ",num[r,c];} printf("\n");

} printf("\n");

 

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

for {r in 1..Nr}{ 

  for{c in 1..Nc}{ printf"  %s",substr(" |H",bv1[r,c]+bv2[r,c]+1,1);} printf(" \n");

  for{c in 1..Nc}{ printf"%s %s",substr(" -=",1+bh1[r,c]+bh2[r,c],1),

                                                                   if ini1[r,c] then abs(ini1[r,c])else substr(" -=|..H",bhv[r,c],1) ;} printf("\n");

} printf("\n");

end;

 

[問題定義コード例]

 

#p01.txt

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

param Nr:= 9;

param Nc:= 9;

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

                                1       0  1  0  5  0  3  0  0 -3

                                2       0  0  0  0  1  0  0  2  0

                                3       4  0  0  8  0  2  0  0  3

                                4       0  2  0  0  2  0  0  2  0

                                5       3  0  0  2  0  1  0  0  3

                                6       0  6  0  0  5  0  0  4  0

                                7       3  0  0  1  0  3  0  0  1

                                8       0  3  0  0  1  0  0  0  0

                                9       3  0  0  3  0  6  0  4  0

;end;

 

 

#p02.txt

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

param Nr:= 9;

param Nc:= 9;

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

                                1       4  0  4  0  1  0  0  0 -2

                                2       0  0  0  0  0  4  0  2  0

                                3       5  0  8  0  2  0  0  0  0

                                4       0  0  0  3  0  7  0  0  3

                                5       0  0  2  0  0  0  0  0  0

                                6       0  0  0  1  0  3  0  1  0

                                7       0  2  0  0  6  0  2  0  0

                                8       0  0  0  0  0  0  0  0  0

                                9       2  0  0  0  4  0  0  0  2

;end;

 

 

トップページへ

 

Ads by TOK2