ぬりめいず - 鉛筆パズルの整数計画法による解法定式化集

鉛筆パズルの整数計画法による解法定式化集７８．
ぬりめいず
http://www.nikoli.co.jp/ja/puzzles/nurimeizu.html
例題（ニコリのパズル紹介より）
解答
Ｓ
Ｇ
Ｓ
Ｇ
○
△
○
△
△
△
ルール
①盤面のいくつかのマスを黒くぬって壁を作り、白マスをたどると
ＳからＧまで通ることができる迷路を作る。
②盤太線で区切られたそれぞれの部屋にあるマスは、すべて黒マスになるか、
すべて白マスになるかのどちらかとする。
③すべての白マスはタテヨコにひとつながりになるが、白マスで輪っかができてはいけない。
④ＳＧ○△があるマスはすべて白マスになる。すべての○は、ＳからＧまでの
最短経路上にあるようにし、すべての△は、最短経路から外れるようにする。
⑤白マスも黒マスも、２×２以上のカタマリになってはいけない。
マスの行番号をＩ、列番号をＪとし、部屋に番号を振り、マス座標との対応を取った表を用意する。
J →
1
2
3
. . . Nc
I 1
↓
1
2
3
4
2
1
2
5
6
3
7
5
5
8
7
9
9
8
.
.
.
Nr
変数
B(I,J) = 1
= 0
マス(I,J)を黒く塗るとき
〃塗らないとき
W(I,J) = 1
= 0
マス(I,J)を黒く塗らないとき
〃塗るとき
TB(K) =
=
TW(K) =
=
部屋(K)を黒く塗るとき
〃塗らないとき
1
0
1
0
部屋(K)を黒く塗らないとき
〃塗るとき
C(I,J) = 1
= 0
マス(I,J)がＳからＧへの最短経路のとき
〃でないとき
R(I,J) =
=
L(I,J) =
=
白マス(I,J)に右向き矢印が付くとき
〃付かないとき
1
0
1
0
白マス(I,J)に左向き矢印が付くとき
〃付かないとき
U(I,J) = 1
= 0
白マス(I,J)に上向き矢印が付くとき
〃付かないとき
白マス(I,J)に下向き矢印が付くとき
〃付かないとき
D(I,J) = 1
= 0
bR(I,J) =
=
bL(I,J) =
=
黒マス(I,J)に右向き矢印が付くとき
〃付かないとき
1
0
1
0
黒マス(I,J)に左向き矢印が付くとき
〃付かないとき
bU(I,J) = 1
= 0
黒マス(I,J)に上向き矢印が付くとき
〃付かないとき
黒マス(I,J)に下向き矢印が付くとき
〃付かないとき
bD(I,J) = 1
= 0
bRD(I,J) =
=
bLD(I,J) =
=
1
0
1
0
bRU(I,J) = 1
= 0
bLU(I,J) = 1
= 0
黒マス(I,J)に右下向き矢印が付くとき
〃付かないとき
黒マス(I,J)に左下向き矢印が付くとき
〃付かないとき
黒マス(I,J)に右上向き矢印が付くとき
〃付かないとき
黒マス(I,J)に左上向き矢印が付くとき
〃付かないとき
目的関数
minimize
x
（ダミー）
制約式
subject to
１．マスは白または黒である
B(I,J)+W(I,J) ＝ 1
(I=1,2,....Nr)
(J=1,2,....Nc)
２．記号入りマスは白マスである
W(I,J) ＝ 1
(I,J)は盤中の記号マス
３．部屋は白または黒である
TB(K)+TW(K) ＝ 1
(K=1,2,....Nt)
Ntは部屋総数
４．部屋Kが黒のときの黒マスB(I,J)
(K=1,2,....Nt)
(I,J)は部屋とマス座標との対応表から
TB(K) ≦ B(I,J)
５．部屋Kが白のときの白マスW(I,J)
(K=1,2,....Nt)
(I,J)は部屋とマス座標との対応表から
TW(K) ≦ W(I,J)
６．白マスは２ｘ２の塊にならない
W(I,J)+W(I+1,J)+W(I+1,J+1)+W(I,J+1)≦ 3
(I=1,2,....Nr-1)
(J=1,2,....Nc-1)
７．黒マスは２ｘ２の塊にならない
B(I,J)+B(I+1,J)+B(I+1,J+1)+B(I,J+1)≦ 3
(I=1,2,....Nr-1)
(J=1,2,....Nc-1)
８．白マスには隣接白マスがある
W(I,J)≦ W(I-1,J)+W(I+1,J)+W(I,J-1)+W(I,J+1)
(I=1,2,....Nr)
(J=1,2,....Nc)
９．白マスに矢印を付ける
W(I,J)≦ U(I,J)+D(I,J)+L(I,J)+R(I,J)
(I=1,2,....Nr)
(J=1,2,....Nc)
但し、Ｇマスを除く
１０．黒マスには矢印がない
B(I,J)+U(I,J)+D(I,J)+L(I,J)+R(I,J)≦ 1
(I=1,2,....Nr)
(J=1,2,....Nc)
１１．枠から外に向く矢印はない
(J=1,2,....Nc)
U(1,J) ＝ 0
D(Nr,J) ＝ 0
L(I,1) ＝ 0
R(I,Nc) ＝ 0
(I=1,2,....Nr)
１２．矢印は黒マスに向かない
B(I,J)+D(I-1,J)≦
B(I,J)+U(I+1,J)≦
B(I,J)+R(I,J-1)≦
B(I,J)+L(I,J+1)≦
1
1
1
1
１３．矢印の対向禁止
R(I,J)+L(I,J+1)≦ 1
D(I,J)+U(I+1,J)≦ 1
(I=1,2,....Nr)
(J=1,2,....Nc)
(I=1,2,....Nr)
(J=1,2,....Nc-1)
(I=1,2,....Nr-1)
(J=1,2,....Nc)
１４．Ｓ（スタート）マスのC(I,J)=1（最短経路に所属するマス）と置く
C(I,J)＝ 1
(I,J)はＳマスの座標
１５．○マスのC(I,J)=1とする
C(I,J)＝ 1
(I,J)は○マスの座標
１６．△マスのC(I,J)=0とする
C(I,J)＝ 0
(I,J)は△マスの座標
１７．Ｓマスに入る矢印の付いたマスはC(I,J)=0とする
C(I-1,J)+D(I-1,J)≦
C(I+1,J)+U(I+1,J)≦
C(I,J-1)+R(I,J-1)≦
C(I,J+1)+L(I,J+1)≦
(I,J)はＳマスの座標
1
1
1
1
１８．流入する矢印のないマスはC(I,J)=0とする
C(I,J)≦ U(I+1,J)+D(I-1,J)+L(I,J+1)+R(I,J-1)
(I=1,2,....Nr)
(J=1,2,....Nc)
１９．C(I,J)=1のマスの矢印方向マスもC(II,JJ)=1とする
C(I,J)+U(I,J)-C(I-1,J)≦
C(I,J)+D(I,J)-C(I+1,J)≦
C(I,J)+L(I,J)-C(I,J-1)≦
C(I,J)+R(I,J)-C(I,J+1)≦
1
1
1
1
(I=1,2,....Nr)
(J=1,2,....Nc)
２０．C(I,J)=1のマスのＴ字配置禁止（分岐があってはならない）
C(I,J)+C(I,J+1)+C(I,J+2)+C(I+1,J+1)≦
C(I,J)+C(I,J+1)+C(I,J+2)+C(I-1,J+1)≦
C(I,J)+C(I+1,J)+C(I+2,J)+C(I+1,J+1)≦
C(I,J)+C(I+1,J)+C(I+2,J)+C(I+1,J-1)≦
3
3
3
3
(I=1,2,....Nr)
(J=1,2,....Nc)
C(I-1,J)+C(I+1,J)+C(I,J-1)+C(I,J+1)＝ 1
(I,J)はＧマスの座標
２１．Ｇマスに接するC(I,J)=1のマスは１個だけ
以下は、白マスが輪っかにならない、全体がタテヨコひとつながりになるように
黒マスに矢印を付けて制御する条件である。このためには、黒マスがタテヨコ斜めに
接して外枠に繋がっていればよい。
２２．黒マスに矢印を１個付ける（タテ・ヨコ・ナナメ、８本の内のどれか）
B(I,J)＝ bU(I,J)+bD(I,J)+bL(I,J)+bR(I,J)
bLU(I,J)+bLD(I,J)+bRU(I,J)+bRD(I,J)
(I=1,2,....Nr)
(J=1,2,....Nc)
２３．白マスに黒矢印は付かない
bigM*{1-W(I,J)}≧ bU(I,J)+bD(I,J)+bL(I,J)+bR(I,J)
bLU(I,J)+bLD(I,J)+bRU(I,J)+bRD(I,J)
(I=1,2,....Nr)
(J=1,2,....Nc)
２４．周辺枠付き黒マスには外向き黒矢印を付ける
B(1,J)≦ bU(1,J)
B(Nr,J)≦ bU(Nr,J)
B(I,1)≦ bL(I,1)
B(I,Nc)≦ bL(I,Nc)
(J=1,2,....Nc)
(I=2,3,....Nr-1)
盤の４隅マスが矢印２本にならないよう注意
２５．黒矢印は白マスに向かない
W(I,J)+bD(I-1,J)≦ 1
W(I,J)+bLD(I-1,J+1)≦
W(I,J)+bLD(I-1,J-1)≦
W(I,J)+bU(I+1,J)≦ 1
W(I,J)+bLU(I+1,J+1)≦
W(I,J)+bRU(I+1,J-1)≦
W(I,J)+bR(I,J-1)≦ 1
W(I,J)+bL(I,J+1)≦ 1
(I=1,2,....Nr)
(J=1,2,....Nc)
1
1
1
1
２６．黒矢印の隣マスとの対向禁止
bR(I,J)+bL(I,J+1)≦ 1
bRU(I,J)+bLD(I-1,J+1)≦
bRD(I,J)+bLU(I+1,J+1)≦
bD(I,J)+bU(I+1,J)≦ 1
bLD(I,J)+bRU(I+1,J-1)≦
bRD(I,J)+bLU(I+1,J+1)≦
(I=1,2,....Nr)
(J=1,2,....Nc)
1
1
1
1
２７．黒矢印は辺隣接を優先し、タテヨコ矢印があればナナメ矢印は付けない
B(I,J+1)+bRU(I,J)+bRD(I,J)≦
B(I,J-1)+bLU(I,J)+bLD(I,J)≦
B(I+1,J)+bLD(I,J)+bRD(I,J)≦
B(I-1,J)+bLU(I,J)+bRU(I,J)≦
1
1
1
1
(I=1,2,....Nr)
(J=1,2,....Nc)
上下界
bounds
変数型
binary
B(I,J) W(I,J) C(I,J)
(I=1,2….…Nr)
(J=1,2….…Nc)
TB(K) TW(K)
(K=1,2….…Nt)
L(I,J) D(I,J) R(I,J) U(I,J)
bL(I,J) bD(I,J) bR(I,J) bU(I,J)
bLD(I,J) bRD(I,J) bRU(I,J) bLU(I,J)
(I=1,2….…Nr)
(J=1,2….…Nc)
general
終端
end
参考に、黒マスと白マスそれぞれに付加した矢印の出力例を示す。
http://puzzleblog542.blog.fc2.com/blog-category-69.html
トクナキラのパズル製造工場ぬりめいず 18×10 おてごろから
１）黒マス矢印
Ｓ
Ｇ
○
△
△
△
△
△
△
白マスは全体がタテヨコに繋がっていなければならないが、「輪っかになってはいけない」
というのは有難いルールである。黒マスを繋いだ矢印が盤の外枠から抜け出していればよい
からである。
２）白マス矢印
Ｓ
Ｇ
○
△
△
△
△
△
△
白マスに１個矢印を付ける（Ｇマスは例外）。矢印は黒マスには向かない。隣マスとの対向矢印は
ない。とすると、Ｇマスに流れ込む矢印群が描ける。矢印はマスに１個であるから、合流はあるが
分流はない。ここでＳマスから出発して、矢印を辿って行けば、この壁配置のときの最短経路に
なるが、矢印を辿るという簡単なことがなかなか難しい。最短経路のマスをC(I,J)=1とするのは
やさしいが、最短経路でないマスをC(I,J)=0とするのが難しいのである。
なお、最短経路であるから、いつも遊んでいる
minimize
命令を生かして
Nr Nc
Σ
Σ C(I,J)＝x
I=1 J=1
として
minimize
x
が必要かと思ったが、必要なさそうである。

Download Report