1. No category

フィルオミノ
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 の範囲に限定することにより、ファイルは相当
縮小されるが、パンクが防げるまでにはならない。