フィルオミノ http://www.nikoli.co.jp/ja/puzzles/fillomino.htmlより解答例題（パズル紹介） 2 1 3 2 6 2 3 1 3 2 3 3 2 6 3 3 5 2 3 3 2 2 4 2 4 5 3 5 3 5 3 3 2 2 1 3 3 3 2 4 5 1 2 2 6 6 6 3 4 4 4 6 3 3 5 3 2 2 4 4 3 4 6 3 3 4 2 1 2 6 ルール以下の条件に従って、全てのマスに数字を入れる。 ①同じ数字が入って隣接するマスは同一区画に属する。 ②同一区画に属するマスの数は、その区画に入る数字と一致する。この例題は簡単であるが、一般には、近くにある同じ数字が同一区画なのか、別区画なのか判断が付かず、また初期に数字が与えられず、終わってみないと何マスの区画なのかわからない区画が発生するのがフィルオミノの難しいところである。必然的に変数の数は多くなり、CPLEX形式の入力ファイルを作ると、数十万から数百万行になり、整数計画法プログラムはメモリー不足エラーで停止する。簡単な問題しか解けないが、対策は考えないことにする。CPLEX形式は、フィルオミノに向かない。不向きなもので対策を考えるのは損である。整数計画法プログラムも、もっと良いものがあるかもしれないからである。 J → 1 2 I 1 ↓ 2 変数マスの行番号をＩ、列番号をＪとして 3 . . . B(I,J,K) ＝1 マス(I,J)に数字 K が入るとき＝0 〃入らないとき Nr 2 3 4 . . . 4 Nc 2 1 3 3 3 L(I,J,K) ＝1 マス(I,J)の左マスが数字 K の同一ブロックのマスのとき〃マスでないとき＝0 D(I,J,K) ＝1 マス(I,J)の下マスが数字 K の同一ブロックのマスのとき〃マスでないとき＝0 R(I,J,K) ＝1 マス(I,J)の右マスが数字 K の同一ブロックのマスのとき〃マスでないとき＝0 U(I,J,K) ＝1 マス(I,J)の上マスが数字 K の同一ブロックのマスのとき〃マスでないとき＝0 C(I,J,II,JJ,K) ＝1 マス(I,J)とマス(II,JJ)が数字 K の同一ブロックのとき〃でないとき＝0 （この５次元配列変数がパンクの原因になっているが、これがないと定式化困難）目的関数 minimize （ダミー） x 制約式 subject to １．マスには１∼Nmaxまでの、どれかの数字が入る。 Nmax B (I,J ,K) = 1 Σ K=1 (I=1,2….…Nr) (J= 1,2.…… Nc ) Nmaxは最大のブロックのマス数で、盤面に与えられた数字の最大値＋１としておく。自然発生ブロックの大きさが、これ以上になる問題は見たことがない。２．数字のが与えられたマスの数値はセットしておく。 B (I,J ,K) = 1 (I,Jは盤面で数字Kが与えられたマスの座標）３．K=1のマスには隣接するマスがなく、K>2のマスには、隣接するマスがある。 B(I,J,K)+B(I,J-1,K) ≦ 1 B(I,J,K)+B(I,J+1,K) ≦ 1 B(I,J,K)+B(I-1,J,K) ≦ 1 B(I,J,K)+B(I+1,J,K) ≦ 1 (I=1,2….…Nr) (J= 1,2.…… Nc ) (K=1) B(I-1,J,K)+B(I,J-1,K)+B(I+1,J,K)+B(I,J+1,K) ≧ B(I,J,K) (I=1,2….…Nr) (J= 1,2.…… Nc ) (K=2,3.....Nmax) ４．左に同一数字マスがあるときL(I,J,K)=1 などだから (I=1,2….…Nr) L(I,J,K)+D(I,J,K)+R(I,J,K)+U(I,J,K) ＝ 0 (J= 1,2.…… Nc ) (K=1) B(I,J,K)+B(I,J-1,K)-L(I,J,K) ≦ 1 (I=1,2….…Nr) B(I,J,K) ≧ L(I,J,K) (J= 1,2.…… Nc ) B(I,J-1,K) ≧ L(I,J,K) (K=2,3.....Nmax) B(I,J,K)+B(I,J+1,K)-R(I,J,K) ≦ 1 B(I,J,K) ≧ R(I,J,K) B(I,J+1,K) ≧ R(I,J,K) B(I,J,K)+B(I-1,J,K)-U(I,J,K) ≦ 1 B(I,J,K) ≧ U(I,J,K) B(I-1,J,K) ≧ U(I,J,K) B(I,J,K)+B(I+1,J,K)-D(I,J,K) ≦ 1 B(I,J,K) ≧ D(I,J,K) B(I+1,J,K) ≧ D(I,J,K) ５．数字３以上のマスの２連孤立禁止。横 R(I,J,K) ≦ B(I-1,J,K)+B(I,J-1,K)+B(I+1,J,K)+B(I-1,J+1,K)+B(I+1,J+1,K)+B(I+1,J+2,K) (I=1,2….…Nr) (J= 1,2.…… Nc-1) (K=3,4.....Nmax) 縦 D(I,J,K) ≦ B(I-1,J,K)+B(I,J-1,K)+B(I,J+1,K)+B(I+1,J-1,K)+B(I+1,J+1,K)+B(I+2,J,K) (I=1,2….…Nr-1) (J= 1,2.…… Nc) (K=3,4.....Nmax) ６．C(I,J,II,JJ,K)は(I,J)、(II,JJ)に関して対称である。 C(I,J,II,JJ,K) ＝ C(II,JJ,I,J,K) (I=1,2….…Nr) (J=1,2….…Nc) (II=1,2….…Nr) (JJ=1,2….…Nc) (K=1,2….…Nmax) (ただしII>I, JJ>Jとする) ７．L(I,J,K)=1ならばC(I,J,I,J-1,K)=1であり、L(I,J,K)=0ならばC(I,J,I,J-1,K)=0である。 L(I,J,K) ＝ C(I,J,I,J-1,K) R(I,J,K) ＝ C(I,J,I,J+1,K) U(I,J,K) ＝ C(I,J,I-1,J,K) D(I,J,K) ＝ C(I,J,I+1,J,K) (I=1,2….…Nr) (J=1,2….…Nc) (K=2,3….…Nmax) ８．C(I,J,II,JJ,K)=1のときL(II,JJ,K)=1ならばC(I,J,II,JJ-1,K)=1である。 L(II,JJ,K)+C(I,J,II,JJ,K)-C(I,J,II,JJ-1,K) ≦ 1 R(II,JJ,K)+C(I,J,II,JJ,K)-C(I,J,II,JJ+1,K) ≦ 1 U(II,JJ,K)+C(I,J,II,JJ,K)-C(I,J,II-1,JJ,K) ≦ 1 D(II,JJ,K)+C(I,J,II,JJ,K)-C(I,J,II+1,JJ,K) ≦ 1 (I=1,2….…Nr) (J=1,2….…Nc) (K=2,3….…Nmax) ９．L(II,JJ,K)=1のときC(I,J,II,JJ,K)=0ならばC(I,J,II,JJ-1,K)=0である。 C(I,J,II,JJ-1,K) C(I,J,II,JJ-1,K) 同様に C(I,J,II,JJ+1,K) C(I,J,II-1,JJ,K) C(I,J,II+1,JJ,K) ≦ C(I,J,II,JJ,K) に 1-L(II,JJ,K)のbig-Mを載せて ≦ C(I,J,II,JJ,K)+ M*｛1-L(II,JJ,K)｝ (I=1,2….…Nr) (J=1,2….…Nc) ≦ C(I,J,II,JJ,K)+ M*｛1-R(II,JJ,K)｝ (K=2,3….…Nmax) ≦ C(I,J,II,JJ,K)+ M*｛1-U(II,JJ,K)｝ ≦ C(I,J,II,JJ,K)+ M*｛1-D(II,JJ,K)｝１０．数字Ｋのブロックの総マス数をＫ個とする。 Nr Nc Σ Σ II=1 JJ=1 C(I,J,II,JJ,K) ＝ K*B(I,J,K) (I=1,2….…Nr) (J=1,2….…Nc) (K=1,2….…Nmax) 上下界 bounds 変数型 binary B(I,J,K) L(I,J,K) R(I,J,K) U(I,J,K) D(I,J,K) C(I,J,II,JJ,K) (I=1,2….…Nr) (J=1,2….…Nc) (K=1,2….…Nmax) (I=1,2….…Nr) (J=1,2….…Nc) (II=1,2….…Nr) (JJ=1,2….…Nc) (K=1,2….…Nmax) 終端 end 変数C(I,J,II,JJ,K)は、｜I-II｜＋｜J-JJ｜＜ K の範囲に限定することにより、ファイルは相当縮小されるが、パンクが防げるまでにはならない。