復元迷路 - 鉛筆パズルの整数計画法による解法定式化集

鉛筆パズルの整数計画法による解法定式化集９３．
復元迷路
解答
例題（2015.7.11毎日新聞より）
ルール
左上から右下まで、すべてのマスを一度ずつ通るルートを見つける。
①あらかじめ入っている線は必ずルートの一部となる。
②進めるのはタテかヨコのみで、ナナメに進んだり、一度通ったマスを通ってはいけない。
変数
マスの行番号をＩ、列番号をＪとして、マスにルートに従った矢印を付けて行く。
U(I,J) ＝1
＝0
D(I,J) ＝1
＝0
L(I,J) ＝1
＝0
R(I,J) ＝1
＝0
N(I,J) ＝K
(I,J)の矢印が上に向いているとき
〃いないとき
J →
1 2
(I,J)の矢印が下に向いているとき
〃いないとき
(I,J)の矢印が左に向いているとき
〃いないとき
(I,J)の矢印が右に向いているとき
〃いないとき
(I,J)の矢印Ｋ番目とき
I 1
↓ 2
3
.
.
.
Nr
3
4
. . .
Nc
目的関数
minimize
x
（ダミー）
制約式
subject to
１．マスから出る矢印は1個
L(I,J)+R(I,J)+U(I,J)+D(I,J) ＝ 1
右下終点マスのとき
L(I,J)+R(I,J)+U(I,J)+D(I,J) ＝ 0
(I=1,2,....Nr)
(J=1,2,....Nc)
２．マスに入る矢印は１個である
L(I,J+1)+R(I,J-1)+U(I+1,J)+D(I-1,J) ＝ 1
左上始点マスのとき
L(I,J+1)+U(I+1,J) ＝ 0
(I=1,2,....Nr)
(J=1,2,....Nc)
３．矢印の先に矢印の根元が付く
L(I,J) ≦ L(I,J-1)+U(I,J-1)+D(I,J-1)
R(I,J) ≦ R(I,J+1)+U(I,J+1)+D(I,J+1)
U(I,J) ≦ U(I-1,J)+L(I-1,J)+R(I-1,J)
D(I,J) ≦ D(I+1,J)+U(I+1,J)+D(I+1,J)
(I=1,2,....Nr)
(J=1,2,....Nc)
４．外枠から外に向かう矢印はない
L(I,1) ＝ 0
R(I,Nc) ＝ 0
U(1,J) ＝ 0
D(Nr,J) ＝ 0
(I=1,2,....Nr)
(J=1,2,....Nc)
５．盤面指定経路
┏に曲がるマスの座標を(I,J)として
R(I,J-1)+D(I-1,J)+L(I,J)+U(I,J) ＝ 0
┗に曲がるマスの座標を(I,J)として
R(I,J-1)+U(I+1,J)+L(I,J)+D(I,J) ＝ 0
┛に曲がるマスの座標を(I,J)として
L(I,J+1)+U(I+1,J)+R(I,J)+D(I,J) ＝ 0
┓に曲がるマスの座標を(I,J)として
L(I,J+1)+D(I-1,J)+R(I,J)+U(I,J) ＝ 0
２連水平記号の左マスの座標を(I,J)として
R(I,J)+L(I,J+1) ＝ 1
３連水平記号の左端マスの座標を(I,J)として
R(I,J)+L(I,J+1) ＝ 1
R(I,J+1)+L(I,J+2) ＝ 1
U(I,J+1)+D(I,J+1)+U(I+1,J+1)+D(I-1,J+1) ＝ 0
２連鉛直記号の上マスの座標を(I,J)として
D(I,J)+U(I+1,J) ＝ 1
３連鉛直記号の上端マスの座標を(I,J)として
D(I,J)+U(I+1,J) ＝ 1
D(I+1,J)+U(I+2,J) ＝ 1
R(I+1,J)+L(I+1,J)+R(I+1,J-1)+L(I+1,J+1) ＝ 0
６．矢印に番号を振る
左上マスに１番を振る。
N(1,1) ＝ 1
のとき N(I,J)+1 ≦ N(I,J+1)
その他 R(I,J) = 1
すなわち矢の先に繋がる矢印の番号が大きくなるように振る。
ビッグＭを使って
(I=1,2,....Nr)
N(I,J)+1 ≦ N(I,J+1)+bigM*{1-R(I,J)}
(J=1,2,....Nc)
同様に
bigM＝Nr*Nc とする
N(I,J)+1 ≦ N(I,J-1)+bigM*{1-L(I,J)}
N(I,J)+1 ≦ N(I-1,J)+bigM*{1-D(I,J)}
N(I,J)+1 ≦ N(I+1,J)+bigM*{1-U(I,J)}
上下界
bounds
N(I,J)≦ bigM
変数型
binary
L(I,J) R(I,J)
U(I,J) D(I,J)
(I=1,2….…Nr)
(J=1,2….…Nc)
general
N(I,J)
(I=1,2….…Nr)
(J=1,2….…Nc)
終端
end
このパズルでは、経路がすべてのマスを一度ずつ通らなければならない。
この条件が付くと、問題を作るとき、盤のタテ・ヨコのマス数を自由に選ぶことができなくなる。
①
②
③ ④
⑤
⑥
すなわち、左図のように白黒模様をつ付けて、経路に沿って
番号を付けて行くと、どんな経路を取っても、偶数番目が
黒マスである。したがって、全体のマスが偶数個の盤では
最終マスとなる右下のマスは黒マスでなければならない。
この例ではもう1行足して８ｘ８とすると解がなくなる。

Download Report