GLPKによるパズル解法 フィルオミノ

キューブ王

最初のものから2回修正を加えている。

(1)   rootN[r,c,n]のサーチ範囲を狭める部分のバグ修正(20190131)

(2)   wd[r,c]=0となる部分を、前処理時点で明示(20190212)

 

 [はじめに]

ニコリの「フィルオミノ」パズルの求解コードを、GLPKMathProg言語で記述してみた。この[フィルオミノ]という名称は、「埋める」を意味する fill とポリオミノの -omino を合成して作られているのだそうだ(wikipedia)。フィルオミノパズル、好きになれなくて、攻略(解法の記述)しようとも思わなかった。しかし、インターネットのあるページに以下の記述があったので、攻略することにした。

---------------(

 ただ、ソルバーを作るのはかなり面倒らしく、ググってもそれらしきものは見つかりませんでした。と言うか定食パズルなのにnikoli.comFlashが存在しないという特殊なパズルなので(シャカシャカはあるのに……)、ソルバを配布したらその道では有名になれるかもしれません

)---------------

最初2013年頃にトライした。一応、解法コードを記述したのだが、予想通りかなり遅いコードとなった。7*7問題を300sec程度掛っていた。それで一旦、投げ捨てていた。

2019年になって、再度トライした。基本的な部分では殆ど進歩しなかったのだが、コードの配置位置を調整することなどで、ある程度速くなった。それで紹介することにした。

 

[ルール]

1. すべてのマスに数字を1つずつ入れ、さらに点線の上にタテヨコに線を引いて、盤面をいくつかのブロックに分けましょう。

2. 同じ数字が入ったマスがタテヨコに隣り合っている場合、それらは同じブロックに入ります。

3. ブロックに入るマスの数は、そのブロックに入る数字と同じになるようにします。

 

[難しさ]

以上の3つがルールである。漫然と読めば、難しい(orいやらしい)ルールとは思えない。しかし、答えを見ると、いやらしさが明らかになる。特に、よく似たパズル「塗り壁」と対比してみれば、いやらしさがよく分かる。

 

 

 

フィルオミノは、ブロック分けに黒い辺を使用する。塗り壁は、ブロック分けに黒いマスを使用する。この違いに注意。なお、塗り壁の解答内にある数字はブロック内のマス数を数えるためのものであるが、解答図としては本来いらないものである。さて、フィルオミノのいやらしさ。

(a)    個別のブロックに、予め指定された数字が1つずつ入ってくれればいいのだが、そうではない。0個、1個、2個、3個と入っている。これがいやらしい。机上で人間が解く場合にそれほどいやらしくないともいえるが、計算機で解く場合にはかなりいやらしい。

(b)   個別のブロックを識別するには、計算機解法の場合ブロックidを与える必要があるかと思うが、塗り壁の場合予め指定された数字のマス位置をブロックidとすればよかった。しかし、このパズルの場合それが通用しない。ブロック内の指定数字が0個や複数個になるからである。今は、最上位の最左のマス位置(青色マス)にしてある。

(c)    さらに、個別ブロック内のマス数を(コンピュータで)数え挙げる際の(木構造の)ルート位置、塗り壁では当然数字指定位置でいいが、フィルオミノでは未定。今は、これも最上位の最左のマス位置(青色マス)にしてある。

以上のようなことで、フィルオミノを計算機で(特に整数計画法で)解く場合、極端に遅くなることが予想された。しかし、兎に角、解法を記述してみることにした。

 

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

問題定義、解答、作業用の配列を示しておく。

 

配列ini[,]は問題定義配列。配列ban[,]は解答配列。配列gid[,]はグループid配列。配列nban[,]はブロック内マス数を数え上げる配列である。なお、gid[,]には、個別のマスにid番号が入っているのだが、ルート位置にだけ数字を表示している。また、nban[,]内の“<>^v”は、マス数を数え挙げるための木構造の有向辺を示している。

 これらの図の内、右の3つにはマスをグループ分けするための仕切り線([難しさ節]では黒い辺)が追加されている。この仕切り線は、隣接する2つのマスのban[,]gid[,]の値が異なっている場合に表示されたもの。

 

 

隣接する2つのマスのban[,]の値が異なっているかどうかは、OPud[,],OPlr[,]という変数の値で管理されている。なおOPは”open”のつもりである。

 

   OPud[r,c]=1  <---> ban[r-1,c] = ban[r,c]  <--->  ban[r,c]の上の辺が黒くない           (1)

   OPlr[r,c]=1  <---> ban[r,c-1] = ban[r,c]   <--->  ban[r,c]の左の辺が黒くない                         (2)

 

nban[,]中の”<>^v”は、変数wr[,],wl[,],wu[,],wd[,]の値を反映している。塗り壁パズルで使用したものと同様。ここでは説明しない。

なお盤面は、本来のものよりも、上下、左右に1つずつマスを追加してある。本来の盤面の最上最左の位置は[1,]である。

 

[解法コード]

解法コード、少し説明しておく。

 

## +++++++++++ Fillomino +++++++++++++++++++++++++++

           param Nr integer;                                                          # number of rows

           param Nc integer;                                                         # number of columns

           param N:=Nr*Nc;                                                          # number of cells

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

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

           var ban{0..Nr+1,0..Nc+1} >=0;                                           # board to answer the problem

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

s.t. OUTER0{r in 0..Nr+1,c in 0..Nc+1: r=0||r=Nr+1||c=0||c=Nc+1}: ban[r,c]=0;      # outer(or walls) cells have not number

s.t. Binnr1{r in 1..Nr,c in 1..Nc}: ban[r,c]>=1;                                    # inner cells: ban[r,c]>=1

 

さて、param Nrは問題の盤面の行数、param Ncは列数である。Param Nはマス数である。ブロックに与える識別番号の最大値でもある。

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

変数ban[,]は、個別マスの番号を格納するもの。解答の基本部分。

 

## ------------ doors ----------------------------------

              var OPlr{0..Nr+1,0..Nc+1} binary;     # OPlr[r,c] <-> ban[r,c-1]= ban[r,c]

              var OPud{0..Nr+1,0..Nc+1} binary;   # OPud[r,c] <-> ban[r-1,c]= ban[r,c]

              var GElr{0..Nr+1,0..Nc+1} binary;     # GElr[r,c] --> ban[r,c-1]>=ban[r,c]

              var LElr{0..Nr+1,0..Nc+1} binary;     # LElr[r,c] --> ban[r,c-1]<=ban[r,c]

              var GEud{0..Nr+1,0..Nc+1} binary;   # GEud[r,c] --> ban[r-1,c]>=ban[r,c]

              var LEud{0..Nr+1,0..Nc+1} binary;   # GEud[r,c] --> ban[r-1,c]<=ban[r,c]

 

OPlr[,],OPud[,]は既に説明している。説明略。

GElr[,],LElr[,],GEud[,],LEud[,]はローカルな変数。OPlr[,]OPud[,](1),(2)を満たすようにするために導入した変数。下の黄色い部分を参照。

 

s.t. CLOSED1{r in 1..Nr,c in 1..Nc:ini[r,c]=1}: OPlr[r,c]+OPlr[r,c+1]+OPud[r,c]+OPud[r+1,c]=0;

s.t. CLOSED2{r in 1..Nr,c in 1..Nc:ini[r,c]=2}: OPlr[r,c]+OPlr[r,c+1]+OPud[r,c]+OPud[r+1,c]=1;

s.t. CLOSED3{r in 1..Nr,c in 1..Nc:ini[r,c]=3}: OPlr[r,c]+OPlr[r,c+1]+OPud[r,c]+OPud[r+1,c]<=2;

s.t. CLOSED4{r in 1..Nr,c in 1..Nc:ini[r,c]=4}: OPlr[r,c]+OPlr[r,c+1]+OPud[r,c]+OPud[r+1,c]<=3;

s.t. CLOSED5{r in 1..Nr,c in 1..Nc-1:ini[r,c]>=1&&ini[r,c+1]>=1&&ini[r,c]!=ini[r,c+1]}: OPlr[r,c+1]=0;

s.t. CLOSED6{r in 1..Nr-1,c in 1..Nc:ini[r,c]>=1&&ini[r+1,c]>=1&&ini[r,c]!=ini[r+1,c]}: OPud[r+1,c]=0;

s.t. CLOSED7{r in 1..Nr-1,c in 1..Nc-1: ini[r,c]=2&&ini[r+1,c+1]=2}: OPlr[r,c+1]+OPud[r+1,c]+OPud[r+1,c+1]+OPlr[r+1,c+1]=0;

s.t. CLOSED8{r in 1..Nr-1,c in 1..Nc-1: ini[r+1,c]=2&&ini[r,c+1]=2}: OPlr[r,c+1]+OPud[r+1,c]+OPud[r+1,c+1]+OPlr[r+1,c+1]=0;

s.t. OPEN000{r in 1..Nr,c in 1..Nc-1:ini[r,c]>=1&&ini[r,c]=ini[r,c+1]}: OPlr[r,c+1]=1;

s.t. OPEN001{r in 1..Nr-1,c in 1..Nc:ini[r,c]>=1&&ini[r,c]=ini[r+1,c]}: OPud[r+1,c]=1;

s.t. EXPAND0{r in 2..Nr,c in 2..Nc}: 1-OPud[r,c]<=1-OPud[r,c-1]+1-OPlr[r-1,c]+1-OPlr[r,c];

s.t. EXPAND1{r in 2..Nr,c in 1..Nc-1}: 1-OPud[r,c]<=1-OPud[r,c]+1-OPlr[r-1,c+1]+1-OPlr[r,c+1];

s.t. EXPAND2{r in 2..Nr,c in 2..Nc}: 1-OPlr[r,c]<=1-OPud[r,c-1]+1-OPlr[r-1,c]+1-OPud[r,c];

s.t. EXPAND3{r in 2..Nr,c in 2..Nc}: 1-OPlr[r,c]<=1-OPud[r+1,c-1]+1-OPlr[r+1,c]+1-OPud[r+1,c];

 

ここの制約CLOSEDn,OPENn,EXPANDnは、問題定義配列ini[r,c]の内、数字が予め指定されたマス位置についての制約。

CLOSED1の場合、ini[r,c]=1であり、その場合セル[r,c]を囲む4つの辺全てが(白でなく)黒い、というもの。

CLOSED2の場合、ini[r,c]=2であり、その場合セル[r,c]を囲む4つの辺の内の3つが(白でなく)黒い、というもの。

以下略。但し、最初の8つの概念図を示しておく。

 

 

s.t. CGElr{r in 1..Nr,c in 1..Nc+1}: 1/N*(1+ban[r,c-1]-ban[r,c])<=GElr[r,c];          # ban[r,c-1]>=ban[r,c]-->GElr[r,c]

s.t. CLElr{r in 1..Nr,c in 1..Nc+1}: 1/N*(1+ban[r,c]-ban[r,c-1])<=LElr[r,c];           # ban[r,c-1]<=ban[r,c]-->LElr[r,c]

s.t. COPlr{r in 1..Nr,c in 1..Nc+1}: GElr[r,c]+LElr[r,c]<=1+OPlr[r,c];                    # ban[r,c-1] =ban[r,c]-->OPENlr[r,c]

s.t. CGEud{r in 1..Nr+1,c in 1..Nc}: 1/N*(1+ban[r-1,c]-ban[r,c])<=GEud[r,c];        #

s.t. CLEud{r in 1..Nr+1,c in 1..Nc}: 1/N*(1+ban[r,c]-ban[r-1,c])<=LEud[r,c];        #

s.t. COPud{r in 1..Nr+1,c in 1..Nc}: GEud[r,c]+LEud[r,c]<=1+OPud[r,c];               #

s.t. Cbanlr0{r in 1..Nr,c in 1..Nc+1}: OPlr[r,c]<=1-1/N*(ban[r,c-1]-ban[r,c]);        # OPENlr[r,c]-->ban[r,c-1]=ban[r,c]

s.t. Cbanlr1{r in 1..Nr,c in 1..Nc+1}: OPlr[r,c]<=1-1/N*(ban[r,c]-ban[r,c-1]);        #

s.t. Cbanud0{r in 1..Nr+1,c in 1..Nc}: OPud[r,c]<=1-1/N*(ban[r-1,c]-ban[r,c]);     # OPENud[r,c]-->ban[r-1,c]=ban[r,c]

s.t. Cbanud1{r in 1..Nr+1,c in 1..Nc}: OPud[r,c]<=1-1/N*(ban[r,c]-ban[r-1,c]);     #

 

ここの10個の制約で(1),(2)の関係を満たすようにしている。少し複雑だが、含意の前件部が変数を含む式なので、そうなった。細かい説明は省略。

 

s.t. CCCC2{r in 1..Nr,c in 1..Nc}: 1/N*(ban[r,c]-1)<=OPud[r,c]+OPlr[r,c+1]+OPud[r+1,c]+OPlr[r,c];  # ban[r,c]>=2-->have open doors

s.t. CCCC1{r in 1..Nr,c in 1..Nc}: 2-ban[r,c]<=1-1/4*(OPud[r,c]+OPlr[r,c+1]+OPud[r+1,c]+OPlr[r,c]);# ban[r,c]==1-->have not open doors

s.t. WALL2h{r in 1..Nr,c in 1..Nc+1: c=1||c=Nc+1}: OPlr[r,c]=0;                         # outer walls are closed, horizontal

s.t. WALL2v{r in 1..Nr+1,c in 1..Nc: r=1||r=Nr+1}: OPud[r,c]=0;                         # outer walls are closed, vertical   

 

制約CCCC2は、ban[r,c]>=2であれば4つの辺の内の1つは黒いというもの。

制約CCCC1は、ban[r,c]==1であれば4つの辺の全てが黒いというもの。制約CLOSED1と類似だが、前件部がini[r,c]==1ban[r,c]==1で異なる。

前者の前件部は定数式、制約式は後件部のみでいい。後者の前件部は変数を含む式、線形計画法での含意の書き方が面倒になる。

 

## ------------ group ----------------------------------

var gid{0..Nr+1,0..Nc+1} >=0;                                 # gid: group id

var root{0..Nr+1,0..Nc+1} binary;                 # root: root cell for counting group menbers

var rootN{0..Nr+1,0..Nc+1,1..12} >=0,<=1;      # root: root cell for counting group members

 

変数gid[,]は、[問題の記述、データ構造]節で説明済み。変数root[r,c], rootN[r,c,n][難しさ]節の青いマスを特定するもの。

3入力のrootN(r,c,n)は、マス[r,c]が値nのブロックのマス数を数えあげるもの。

 

s.t. GROUP0{r in 0..Nr+1,c in 0..Nc+1: r=0||r=Nr+1||c=0||c=Nc+1}: gid[r,c]=0;       # wall[r,c] --> gid[r,c]=0

s.t. GROUP1{r in 1..Nr,c in 1..Nc}: gid[r,c]<=Nc*(r-1)+c;                                 # gid[r,c] <= cell_id[r,c]

s.t. GROUP2{r in 1..Nr,c in 1..Nc}: gid[r,c]+N*(1-root[r,c])>=Nc*(r-1)+c; # root[r,c] --> gid[r,c]=cell_id[r,c]

 

制約GROUP0は、本来の盤面よりも外のマスの番号は0というもの。

制約GROUP1は、マス位置(Nc*(r-1++c))以下の値がgid[r,c]に与えられるというもの。

制約GROUP2は、含意 root[r,c] ---> gid[r,c]=cell_id[r,c]。 前件部が変数で、含意の書き方が少し複雑になった。

 

s.t. Gbanlr0{r in 1..Nr,c in 1..Nc+1}: OPlr[r,c]<=1-1/N*(gid[r,c-1]-gid[r,c]);          # OPENlr[r,c]-->gid[r,c-1]=gid[r,c]

s.t. Gbanlr1{r in 1..Nr,c in 1..Nc+1}: OPlr[r,c]<=1-1/N*(gid[r,c]-gid[r,c-1]);          #

s.t. Gbanud0{r in 1..Nr+1,c in 1..Nc}: OPud[r,c]<=1-1/N*(gid[r-1,c]-gid[r,c]);       # OPENud[r,c]-->gid[r-1,c]=gid[r,c]

s.t. Gbanud1{r in 1..Nr+1,c in 1..Nc}: OPud[r,c]<=1-1/N*(gid[r,c]-gid[r-1,c]);       #

 

ここの4つの制約も、コメント通りの含意。前件部が変数で、含意の書き方が少し複雑になった。

 

s.t. ROOT01{r in 1..Nr,c in 1..Nc: ini[r,c]=1}: rootN[r,c,1]=1;

s.t. ROOT02{r in 1..Nr,c in 1..Nc: ini[r,c]=2}: sum{r1 in 0..1,c1 in 0..1:r-r1>=1&&c-c1>=1&&r1+c1<=1}rootN[r-r1,c-c1,2] >=1;

s.t. ROOT03{r in 1..Nr,c in 1..Nc: ini[r,c]=3}: rootN[r-1,c+1,3]+sum{r1 in 0..2,c1 in 0..2:r-r1>=1&&c-c1>=1&&r1+c1<=2}rootN[r-r1,c-c1,3] >=1;

s.t. ROOT04{r in 2..Nr,c in 1..Nc: ini[r,c]=4}: sum{r1 in 0..2,c1 in 0..2: r-r1>=0&&c+c1<=Nc&&r1+c1<=2}rootN[r-r1,c+c1,4]

                            + sum{r1 in 0..3,c1 in 0..3:r-r1>=1&&c-c1>=1&&r1+c1<=3}rootN[r-r1,c-c1,4] >=1;

s.t. ROOT05{r in 1..Nr,c in 1..Nc: ini[r,c]=5}: sum{r1 in 0..3,c1 in 0..3: r-r1>=0&&c+c1<=Nc&&r1+c1<=3}rootN[r-r1,c+c1,5]

                            + sum{r1 in 0..4,c1 in 0..4:r-r1>=1&&c-c1>=1&&r1+c1<=4}rootN[r-r1,c-c1,5] >=1;

s.t. ROOT06{r in 1..Nr,c in 1..Nc: ini[r,c]=6}: sum{r1 in 0..4,c1 in 0..4: r-r1>=0&&c+c1<=Nc&&r1+c1<=4}rootN[r-r1,c+c1,6]

                            + sum{r1 in 0..5,c1 in 0..5:r-r1>=1&&c-c1>=1&&r1+c1<=5}rootN[r-r1,c-c1,5] >=1;

 

ini[r,c]=1,2,3,4,5,6であれば、左上の直角二等辺三角形内か右上の直角3角形内にルート位置があるという制約。これで、root[r,c]or rootN[r,c,n]のサーチ範囲がかなり抑えられる。

かなり速くなった。この部分、従来コードにはバグがあったのだが、直した(190131)

 

s.t. ROOTlr{r in 1..Nr,c in 1..Nc}: OPlr[r,c]<=1-root[r,c];                                 # [r,c-1] OPEN [r,c] --> !root[r,c]

s.t. ROOTud{r in 1..Nr,c in 1..Nc}: OPud[r,c]<=1-root[r,c];                              # [r-1,c] OPEN [r,c] --> !root[r,c]

 

ここの2つの制約は、上の辺や左の辺が黒でなく白であれば、そのセルはrootにはなりえないというもの。

 

以降に、個別ブロックのセル数を数えあげるコードが続くがその部分の説明は省略する。塗り壁問題の場合とほぼ同様だが、root[r,c]が変数であることから複雑さが導入されている。

 

以降、バグ修正に伴い、修正が入っている(190131)

[走行時間]

以下の結果を得ている。

 

 

遅い。6*6程度の問題しか解けない。

しかし、これでも6年前のものに較べると速くなっている。6年前は、p6300sec程度掛っていた。

 

なお、Glpkv4.45 版を使用した際の測定結果。別に、v4.49版とv4.65版もダウンロードしているが、速度はどれも大して変わらないようであるので、v4.45版での測定。

V4.65版は、ダウンロードすれば、glpsolが出来上がっていて、(30分以上かかる)install(or make)不要であった。

 

[走行時間2] 後から追加(20190212)

 微調整して以下のようになった。

 

 

 少し説明しておく。

 このフィルオミノ、root[r,c] or rootN[r,c,n]を試行錯誤的にサーチしていく必要があり、それで遅くなっていると判断できた。

そこでroot[r,c] or rootN[r,c,n]のサーチ範囲を狭めた。それが[走行時間]節の結果である。6年前に較べると、かなり速くなった。

 あと1つ、ブロック内のセル数を数えあげる際の木構造が一つでなく複数個になる。それに伴いサーチが遅くなる。ここでのrootの決め方からは、

wd[r,c]は大抵は0でいい。なら、wd[r,c]が0でいい部分を前処理時点で明示しておけば、木構造の個数が少なくなり、速くなろう。例えば以下。

s.t. OPT97{r in 1..Nr,c in 1..Nc:ini[r,c]<=4}: wd[r,c]=0;

そんな微調整でこの[走行時間2]節の走行時間となったもの。

 

[mathProgコード]

 

## +++++++++++ Fillomino +++++++++++++++++++++++++++

              param Nr integer;                                                                                    # number of rows

              param Nc integer;                                                                                    # number of columns

              param N:=Nr*Nc;                                                                                                  # number of cells

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

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

              var ban{0..Nr+1,0..Nc+1} >=0;                                                                                # board to answer the problem

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

s.t. OUTER0{r in 0..Nr+1,c in 0..Nc+1: r=0||r=Nr+1||c=0||c=Nc+1}: ban[r,c]=0; # outer(or walls) cells have not number

s.t. Binnr1{r in 1..Nr,c in 1..Nc}: ban[r,c]>=1;                                            # inner cells: ban[r,c]>=1

## ------------ doors ----------------------------------

              var OPlr{0..Nr+1,0..Nc+1} binary;     # OPlr[r,c] <-> ban[r,c-1]= ban[r,c]

              var OPud{0..Nr+1,0..Nc+1} binary;   # OPud[r,c] <-> ban[r-1,c]= ban[r,c]

              var GElr{0..Nr+1,0..Nc+1} binary;     # GElr[r,c] --> ban[r,c-1]>=ban[r,c]

              var LElr{0..Nr+1,0..Nc+1} binary;     # LElr[r,c] --> ban[r,c-1]<=ban[r,c]

              var GEud{0..Nr+1,0..Nc+1} binary;   # GEud[r,c] --> ban[r-1,c]>=ban[r,c]

              var LEud{0..Nr+1,0..Nc+1} binary;   # GEud[r,c] --> ban[r-1,c]<=ban[r,c]

s.t. CLOSED1{r in 1..Nr,c in 1..Nc:ini[r,c]=1}: OPlr[r,c]+OPlr[r,c+1]+OPud[r,c]+OPud[r+1,c]=0;

s.t. CLOSED2{r in 1..Nr,c in 1..Nc:ini[r,c]=2}: OPlr[r,c]+OPlr[r,c+1]+OPud[r,c]+OPud[r+1,c]=1;

s.t. CLOSED3{r in 1..Nr,c in 1..Nc:ini[r,c]=3}: OPlr[r,c]+OPlr[r,c+1]+OPud[r,c]+OPud[r+1,c]<=2;

s.t. CLOSED4{r in 1..Nr,c in 1..Nc:ini[r,c]=4}: OPlr[r,c]+OPlr[r,c+1]+OPud[r,c]+OPud[r+1,c]<=3;

s.t. CLOSED5{r in 1..Nr,c in 1..Nc-1:ini[r,c]>=1&&ini[r,c+1]>=1&&ini[r,c]!=ini[r,c+1]}: OPlr[r,c+1]=0;

s.t. CLOSED6{r in 1..Nr-1,c in 1..Nc:ini[r,c]>=1&&ini[r+1,c]>=1&&ini[r,c]!=ini[r+1,c]}: OPud[r+1,c]=0;

s.t. CLOSED7{r in 1..Nr-1,c in 1..Nc-1: ini[r,c]=2&&ini[r+1,c+1]=2}: OPlr[r,c+1]+OPud[r+1,c]+OPud[r+1,c+1]+OPlr[r+1,c+1]=0;

s.t. CLOSED8{r in 1..Nr-1,c in 1..Nc-1: ini[r,c]=2&&ini[r+1,c+1]=2}: OPlr[r,c+1]+OPud[r+1,c]+OPud[r+1,c+1]+OPlr[r+1,c+1]=0;

s.t. CLOSED9{r in 1..Nr-1,c in 1..Nc: ini[r,c]=3&&ini[r+2,c]=3&&(ini[r-1,c]=3||ini[r+3,c]=3)}: OPud[r+1,c]+OPud[r+2,c]=0;

s.t. CLOSED10{r in 1..Nr-1,c in 1..Nc: ini[r,c]=3&&ini[r+1,c]=3&&(ini[r+2,c+1]=3)}: OPlr[r+1,c+1]+OPud[r+2,c]+OPud[r+2,c+1]+OPlr[r+2,c+1]=0;

 

#s.t. CCCC2{r in 1..Nr,c in 1..Nc}: 1/N*(ban[r,c]-1)<=OPud[r,c]+OPlr[r,c+1]+OPud[r+1,c]+OPlr[r,c];  # ban[r,c]>=2-->have open doors

#s.t. CCCC1{r in 1..Nr,c in 1..Nc}: 2-ban[r,c]<=1-1/4*(OPud[r,c]+OPlr[r,c+1]+OPud[r+1,c]+OPlr[r,c]);# ban[r,c]==1-->have not open door

 

s.t. OPEN000{r in 1..Nr,c in 1..Nc-1:ini[r,c]>=1&&ini[r,c]=ini[r,c+1]}: OPlr[r,c+1]=1;

s.t. OPEN001{r in 1..Nr-1,c in 1..Nc:ini[r,c]>=1&&ini[r,c]=ini[r+1,c]}: OPud[r+1,c]=1;

s.t. EXPAND0{r in 2..Nr,c in 2..Nc}: 1-OPud[r,c]<=1-OPud[r,c-1]+1-OPlr[r-1,c]+1-OPlr[r,c];

s.t. EXPAND1{r in 2..Nr,c in 1..Nc-1}: 1-OPud[r,c]<=1-OPud[r,c]+1-OPlr[r-1,c+1]+1-OPlr[r,c+1];

s.t. EXPAND2{r in 2..Nr,c in 2..Nc}: 1-OPlr[r,c]<=1-OPud[r,c-1]+1-OPlr[r-1,c]+1-OPud[r,c];

s.t. EXPAND3{r in 2..Nr,c in 2..Nc}: 1-OPlr[r,c]<=1-OPud[r+1,c-1]+1-OPlr[r+1,c]+1-OPud[r+1,c];

 

s.t. Cbanlr0{r in 1..Nr,c in 1..Nc+1}: OPlr[r,c]<=1-1/N*(ban[r,c-1]-ban[r,c]);              # OPENlr[r,c]-->ban[r,c-1]=ban[r,c]

s.t. Cbanlr1{r in 1..Nr,c in 1..Nc+1}: OPlr[r,c]<=1-1/N*(ban[r,c]-ban[r,c-1]);              #

s.t. Cbanud0{r in 1..Nr+1,c in 1..Nc}: OPud[r,c]<=1-1/N*(ban[r-1,c]-ban[r,c]);           # OPENud[r,c]-->ban[r-1,c]=ban[r,c]

s.t. Cbanud1{r in 1..Nr+1,c in 1..Nc}: OPud[r,c]<=1-1/N*(ban[r,c]-ban[r-1,c]);           #

 

s.t. CGElr{r in 1..Nr,c in 1..Nc+1}: 1/N*(1+ban[r,c-1]-ban[r,c])<=GElr[r,c]; # ban[r,c-1]>=ban[r,c]-->GElr[r,c]

s.t. CLElr{r in 1..Nr,c in 1..Nc+1}: 1/N*(1+ban[r,c]-ban[r,c-1])<=LElr[r,c];  # ban[r,c-1]<=ban[r,c]-->LElr[r,c]

s.t. COPlr{r in 1..Nr,c in 1..Nc+1}: GElr[r,c]+LElr[r,c]<=1+OPlr[r,c];                       # ban[r,c-1] =ban[r,c]-->OPENlr[r,c]

s.t. CGEud{r in 1..Nr+1,c in 1..Nc}: 1/N*(1+ban[r-1,c]-ban[r,c])<=GEud[r,c];            #

s.t. CLEud{r in 1..Nr+1,c in 1..Nc}: 1/N*(1+ban[r,c]-ban[r-1,c])<=LEud[r,c];             #

s.t. COPud{r in 1..Nr+1,c in 1..Nc}: GEud[r,c]+LEud[r,c]<=1+OPud[r,c];                 #

 

s.t. WALL2h{r in 1..Nr,c in 1..Nc+1: c=1||c=Nc+1}: OPlr[r,c]=0;                                          # outer walls are closed, horizontal

s.t. WALL2v{r in 1..Nr+1,c in 1..Nc: r=1||r=Nr+1}: OPud[r,c]=0;                                         # outer walls are closed, vertical

s.t. CCCC2{r in 1..Nr,c in 1..Nc}: 1/N*(ban[r,c]-1)<=OPud[r,c]+OPlr[r,c+1]+OPud[r+1,c]+OPlr[r,c];  # ban[r,c]>=2-->have open doors

s.t. CCCC1{r in 1..Nr,c in 1..Nc}: 2-ban[r,c]<=1-1/4*(OPud[r,c]+OPlr[r,c+1]+OPud[r+1,c]+OPlr[r,c]);# ban[r,c]==1-->have not open door

 

## ------------ group ----------------------------------

              var gid{0..Nr+1,0..Nc+1} >=0,<=N;                 # gid: group id, each group is a conected component

              var root{0..Nr+1,0..Nc+1} binary;                    # root: root cell for counting group members

              var rootN{0..Nr+1,0..Nc+1,1..12} >=0,<=1;      # root: root cell for counting group members

 

s.t. GGGGG0{r in 1..Nr,c in 1..Nc}: sum{n in 1..12}rootN[r,c,n] = root[r,c];

s.t. GROUP0{r in 0..Nr+1,c in 0..Nc+1: r=0||r=Nr+1||c=0||c=Nc+1}: gid[r,c]=0;  # wall[r,c] --> gid[r,c]=0

s.t. GROUP1{r in 1..Nr,c in 1..Nc}: gid[r,c]<=Nc*(r-1)+c;                                         # gid[r,c] <= cell_id[r,c]

s.t. GROUP2{r in 1..Nr,c in 1..Nc}: gid[r,c]+N*(1-root[r,c])>=Nc*(r-1)+c;   # root[r,c] --> gid[r,c]=cell_id[r,c]

/*

s.t. ROOT99: sum{r in 1..Nr,c in 1..Nc,n in 1..12}n*rootN[r,c,n] =N;

s.t. ROOT11: root[1,1]=1;

s.t. ROOT1N{c in 1..Nc-1}: 1-OPlr[1,c]<=root[1,c];

s.t. ROOTlr{r in 1..Nr,c in 1..Nc}: OPlr[r,c]<=1-root[r,c];                           # [r,c-1] OPEN [r,c] --> !root[r,c]

s.t. ROOTud{r in 1..Nr,c in 1..Nc}: OPud[r,c]<=1-root[r,c];                        # [r-1,c] OPEN [r,c] --> !root[r,c]

/* */

s.t. Gbanlr0{r in 1..Nr,c in 1..Nc+1}: OPlr[r,c]<=1-1/N*(gid[r,c-1]-gid[r,c]); # OPENlr[r,c]-->gid[r,c-1]=gid[r,c]

s.t. Gbanlr1{r in 1..Nr,c in 1..Nc+1}: OPlr[r,c]<=1-1/N*(gid[r,c]-gid[r,c-1]); #

s.t. Gbanud0{r in 1..Nr+1,c in 1..Nc}: OPud[r,c]<=1-1/N*(gid[r-1,c]-gid[r,c]);            # OPENud[r,c]-->gid[r-1,c]=gid[r,c]

s.t. Gbanud1{r in 1..Nr+1,c in 1..Nc}: OPud[r,c]<=1-1/N*(gid[r,c]-gid[r-1,c]);            #

/* */

s.t. ROOT01{r in 1..Nr,c in 1..Nc: ini[r,c]=1}: rootN[r,c,1]=1;

s.t. ROOT02{r in 1..Nr,c in 1..Nc: ini[r,c]=2}: sum{r1 in 0..1,c1 in 0..1:r-r1>=1&&c-c1>=1&&r1+c1<=1}rootN[r-r1,c-c1,2] >=1;

s.t. ROOT03{r in 1..Nr,c in 1..Nc: ini[r,c]=3}: rootN[r-1,c+1,3]+sum{r1 in 0..2,c1 in 0..2:r-r1>=1&&c-c1>=1&&r1+c1<=2}rootN[r-r1,c-c1,3] >=1;

s.t. ROOT04{r in 2..Nr,c in 1..Nc: ini[r,c]=4}: sum{r1 in 0..2,c1 in 0..2: r-r1>=0&&c+c1<=Nc&&r1+c1<=2}rootN[r-r1,c+c1,4]

                            + sum{r1 in 0..3,c1 in 0..3:r-r1>=1&&c-c1>=1&&r1+c1<=3}rootN[r-r1,c-c1,4] >=1;

s.t. ROOT05{r in 1..Nr,c in 1..Nc: ini[r,c]=5}: sum{r1 in 0..3,c1 in 0..3: r-r1>=0&&c+c1<=Nc&&r1+c1<=3}rootN[r-r1,c+c1,5]

                            + sum{r1 in 0..4,c1 in 0..4:r-r1>=1&&c-c1>=1&&r1+c1<=4}rootN[r-r1,c-c1,5] >=1;

s.t. ROOT06{r in 1..Nr,c in 1..Nc: ini[r,c]=6}: sum{r1 in 0..4,c1 in 0..4: r-r1>=0&&c+c1<=Nc&&r1+c1<=4}rootN[r-r1,c+c1,6]

                            + sum{r1 in 0..5,c1 in 0..5:r-r1>=1&&c-c1>=1&&r1+c1<=5}rootN[r-r1,c-c1,5] >=1;

 

s.t. ROOT99: sum{r in 1..Nr,c in 1..Nc,n in 1..12}n*rootN[r,c,n] =N;

s.t. ROOT11: root[1,1]=1;

s.t. ROOT1N{c in 1..Nc-1}: 1-OPlr[1,c]<=root[1,c];

s.t. ROOTlr{r in 1..Nr,c in 1..Nc}: OPlr[r,c]<=1-root[r,c];                           # [r,c-1] OPEN [r,c] --> !root[r,c]

s.t. ROOTud{r in 1..Nr,c in 1..Nc}: OPud[r,c]<=1-root[r,c];                        # [r-1,c] OPEN [r,c] --> !root[r,c]

/* */

## ------------ arrows for counting cells in each group ---------------------------

              var wl{0..Nr+1,0..Nc+1} binary;                                                                # <--: link left

              var wr{0..Nr+1,0..Nc+1} binary;                                                                # -->: link right

              var wu{0..Nr+1,0..Nc+1} binary;                                                               #  ^ : link upward

#            var wu{0..Nr+1,0..Nc+1} >=0,<=1;                                               #  ^ : link upward

              var wd{0..Nr+1,0..Nc+1} binary;                                                               #  v : link downward

 

#s.t. OPT10{r in 2..Nr,c in 2..Nc}: wr[r,c-1]+wu[r,c]+wl[r-1,c]+wd[r-1,c-1]<=2;          #inhibit u-turn

#s.t. OPT11{r in 2..Nr,c in 2..Nc}: wu[r,c-1]+wr[r-1,c-1]+wd[r-1,c]+wl[r,c]<=2;          #inhibit u-turn

#s.t. OPT12{r in 2..Nr,c in 2..Nc:ini[r,c-1]=6&&ini[r,c]=6}: wu[r,c-1]+wr[r-1,c-1]+wd[r-1,c]+wl[r,c]<=2;      #inhibit u-turn

#s.t. OPT50{r in 1..Nr}: wl[r,1]=0;

s.t. OPT51{r in 1..Nr}: wr[r,Nc]=0;

#s.t. OPT52{c in 1..Nc}: wu[1,c]=0;

#s.t. OPT95{r in 1..Nr,c in 1..Nc:ini[r,c]=2}: wr[r,c]+wd[r,c]=0;

#s.t. OPT95{r in 1..Nr,c in 1..Nc:ini[r,c]=3}: wr[r,c]<=wu[r,c+1];

s.t. OPT94{r in 1..Nr,c in 1..Nc:ini[r,c]=5&&ini[r+1,c+1]=5}: wd[r,c]=0;

s.t. OPT93{r in 1..Nr,c in 1..Nc:ini[r,c]=5&&ini[r+1,c-1]!=0&&ini[r,c]!=5}: wd[r,c]=0;

s.t. OPT97{r in 1..Nr,c in 1..Nc:ini[r,c]<=4}: wd[r,c]=0;

#s.t. OPT98{r in 1..Nr,c in 1..Nc}: wd[r,c]=0;

#s.t. OPT99{r in 1..Nr,c in 1..Nc}: 0.25*(5-ban[r,c])+wd[r,c]<=1;

#s.t. RRRl1{r in 1..Nr,c in 1..Nc}: wl[r,c]+wr[r,c-1]<=OPlr[r,c];     # wl[r,c]||wr[r,c-1]-->OPlr[r,c]

#s.t. RRRr1{r in 1..Nr,c in 1..Nc}: wr[r,c]+wl[r,c+1]<=OPlr[r,c+1];             # wr[r,c]||wl[r,c+1]-->OPlr[r,c+1]

#s.t. RRRu1{r in 1..Nr,c in 1..Nc}: wu[r,c]+wd[r-1,c]<=OPud[r,c]; # wu[r,c]||wd[r-1,c]-->OPud[r,c]

#s.t. RRRd1{r in 1..Nr,c in 1..Nc}: wd[r,c]+wu[r+1,c]<=OPud[r+1,c];          # wd[r,c]||wu[r+1,c]-->OPud[r+1,c]

s.t. WALL2{r in 0..Nr+1,c in 0..Nc+1: r=0||r=Nr+1||c=0||c=Nc+1}:       # wall[r,c] --> !wl[r,c]&&!wr[r,c]...

                            wl[r,c]+wr[r,c]+wu[r,c]+wd[r,c]=0;

s.t. OPT02{r in 1..Nr,c in 1..Nc: ini[r,c]=1}: wl[r,c]+wr[r,c]+wu[r,c]+wd[r,c]+(1-root[r,c])=0;

s.t. LLL02{r in 1..Nr,c in 1..Nc:ini[r,c]!=1}: wl[r,c]+wr[r,c]+wu[r,c]+wd[r,c]=1-root[r,c];

 

s.t. RRRl1{r in 1..Nr,c in 1..Nc}: wl[r,c]+wr[r,c-1]<=OPlr[r,c];      # wl[r,c]||wr[r,c-1]-->OPlr[r,c]

s.t. RRRr1{r in 1..Nr,c in 1..Nc}: wr[r,c]+wl[r,c+1]<=OPlr[r,c+1]; # wr[r,c]||wl[r,c+1]-->OPlr[r,c+1]

s.t. RRRu1{r in 1..Nr,c in 1..Nc}: wu[r,c]+wd[r-1,c]<=OPud[r,c];  # wu[r,c]||wd[r-1,c]-->OPud[r,c]

s.t. RRRd1{r in 1..Nr,c in 1..Nc}: wd[r,c]+wu[r+1,c]<=OPud[r+1,c];            # wd[r,c]||wu[r+1,c]-->OPud[r+1,c]

## ------------ count cells in the same group ------------------

              var nl{0..Nr+1,0..Nc+1} >=0,<=N;                                               # send number left

              var nr{0..Nr+1,0..Nc+1} >=0,<=N;                                               # send number right

              var nu{0..Nr+1,0..Nc+1} >=0,<=N;                                              # send number upward

              var nd{0..Nr+1,0..Nc+1} >=0,<=N;                                              # send number downward

              var nban{0..Nr+1,0..Nc+1} >=0,<=N;                                           #

 

s.t. MEMBl{r in 0..Nr+1,c in 0..Nc+1}: nl[r,c]<=N*wl[r,c];                         # !wl[r,c] --> nl[r,c]=0

s.t. MEMBr{r in 0..Nr+1,c in 0..Nc+1}: nr[r,c]<=N*wr[r,c];                        # !wr[r,c] --> nr[r,c]=0

s.t. MEMBu{r in 0..Nr+1,c in 0..Nc+1}: nu[r,c]<=N*wu[r,c];                      # !wu[r,c] --> nu[r,c]=0

s.t. MEMBd{r in 0..Nr+1,c in 0..Nc+1}: nd[r,c]<=N*wd[r,c];                      # !wd[r,c] --> nd[r,c]=0

 

s.t. WHT53{r in 1..Nr,c in 1..Nc}: nban[r,c]<=ban[r,c];                               # nban[r,c]<=ban[r,c]

s.t. WHT54{r in 1..Nr,c in 1..Nc}: root[r,c]<=1+1/N*(nban[r,c]-ban[r,c]);# root[r,c]-->nban[r,c]=ban[r,c]

 

s.t. WHT50{r in 1..Nr,c in 1..Nc}:                                                             # recieve numbers from sons

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

s.t. WHT51{r in 1..Nr,c in 1..Nc}:                                                              # send number to one arrow

              nban[r,c]<=  nl[r,c]+nr[r,c]+nu[r,c]+nd[r,c] + N*(root[r,c]);         

s.t. WHT52{r in 1..Nr,c in 1..Nc}:                                                              # send number to one arrow

              nban[r,c]>=  nl[r,c]+nr[r,c]+nu[r,c]+nd[r,c] - N*(root[r,c]);

#s.t. WHT53{r in 1..Nr,c in 1..Nc}: nban[r,c]<=ban[r,c];                             # nban[r,c]<=ban[r,c]

#s.t. WHT54{r in 1..Nr,c in 1..Nc}: root[r,c]<=1+1/N*(nban[r,c]-ban[r,c]);# root[r,c]-->nban[r,c]=ban[r,c]

## ++++++++++ solve and dump ++++++++++++++++++++++++++++

#minimize MMM: sum{r in 1..Nr,c in 1..Nc: r<=3||r>=Nr-2||c<=3||c>=Nc-2} (OPlr[r,c]+OPud[r,c]);

#minimize MMM: sum{r in 1..Nr,c in 1..Nc} (OPlr[r,c]+OPud[r,c]);

minimize MMM: sum{r in 1..Nr,c in 1..Nc} (OPlr[r,c]+OPud[r,c]-0.1*wl[r,c]);

#maximize MMM: sum{r in 1..Nr,c in 1..Nc} (wl[r,c]+wu[r,c]);

solve;

 

printf "--ini---N=%3d\n",N;

for {r in 1..Nr}{ 

  for{c in 1..Nc}{ printf"+%3s","   ";} printf("+\n");

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

}

  for{c in 1..Nc}{ printf"+%3s","   ";} printf("+\n");

 

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

for {r in 1..Nr}{ 

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

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

}

  for{c in 1..Nc}{ printf"+%3s",if OPud[Nr+1,c]then "   "else"---";} printf("+\n");

 

printf "--gid---\n";

for {r in 1..Nr}{ 

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

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

}

  for{c in 1..Nc}{ printf"+%3s",if OPud[Nr+1,c]then "   "else"---";} printf("+\n");

printf "--nban---\n";

for {r in 1..Nr}{ 

  for{c in 1..Nc}{ printf"+%3s",if OPud[r,c]then if wu[r,c]then " ^ "else if wd[r-1,c]then" V "else"   "else"---";} printf("+\n");

#  for{c in 1..Nc}{ printf"+%3s",if OPud[r,c]then if wu[r,c]then " A "else if wd[r-1,c]then" V "else"   "else"---";} printf("+\n");

  for{c in 1..Nc}{ printf"%1s%2.0f ",if OPlr[r,c]then if wl[r,c]then"<"else if wr[r,c-1]then">"else" "else"|",nban[r,c];} printf("|\n");

}

  for{c in 1..Nc}{ printf"+%3s",if OPud[Nr+1,c]then "   "else"---";} printf("+\n");

end;

 

[問題例]

 

#p01.txt

data;

              param Nr:=4;

              param Nc:=4;

              param ini:

               1 2 3 4:=

  1          3 0 0 1

  2          0 3 0 3

  3          2 0 0 0

  4          0 2 0 3

; end;

 

#p02.txt

data;

              param Nr:=5;

              param Nc:=5;

              param ini:

               1 2 3 4 5:=

  1          3 0 1 0 3

  2          0 0 0 0 0

  3          3 0 0 0 3

  4          0 1 0 1 0

  5          3 0 0 0 3

; end;

 

#p03.txt

data;

              param Nr:=5;

              param Nc:=5;

              param ini:

               1 2 3 4 5:=

  1          6 0 0 0 1

  2          0 0 6 0 0

  3          0 6 0 6 0

  4          0 0 6 0 0

  5          6 6 1 6 6

#  5         6 0 0 0 6

; end;

 

#p04.txt

data;

              param Nr:=6;

              param Nc:=6;

              param ini:

               1 2 3 4 5 6:=

  1          4 0 0 0 6 0

  2          4 0 0 6 6 0

  3          5 3 1 0 0 0

  4          0 0 0 1 2 3

  5          0 3 3 0 0 1

  6          0 3 0 0 0 3

; end;

 

#p05.txt

data;

              param Nr:=6;

              param Nc:=6;

              param ini:

               1 2 3 4 5 6:=

  1          5 0 5 0 0 6

  2          0 5 3 0 6 5

  3          0 6 0 0 0 0

  4          0 0 0 0 4 0

  5          6 6 0 4 4 0

  6          1 0 0 5 0 1

; end;

 

#p06.txt

data;

              param Nr:=7;

              param Nc:=7;

              param ini:

               1 2 3 4 5 6 7:=

  1          0 2 0 4 0 2 0

  2          1 0 2 0 6 0 6

  3          3 0 0 3 0 0 3

  4          0 0 0 5 0 0 0

  5          3 0 0 2 0 0 3

  6          3 0 2 0 4 0 2

  7          0 3 0 3 0 1 0

; end;

 

 

トップページへ

Ads by TOK2