鉛筆パズルの整数計画法による解法定式化集８１． 2015.07.07 改訂流れるループ http://puzzleblog542.blog.fc2.com/blog-entry-819.html 解答例題トクナキラのパズル製造工場からルール以下の条件に従って、盤面の白マスを通る単一な、向きのあるループを描く。 ①ループの線は交差、枝別れしない。 ②白マスにある黒矢印は、ループ線がこの矢印方向に直進しなければならないことを表す。 ③黒マス中の白矢印は、その黒マスから矢印の方向に、別の黒マスまたは外枠まで風が吹くことを表し、風が吹いているマスに横から入ったループ線は、風の方向に曲がらなければならない。ループは単一なので、どこか（黒矢印のどれか）で切り、そこから通過マスに番号を振って行けば、全体が一つに繋がる。風の吹いているマスは最初から決まっているので、座標と風向を入れたデータセットを用意しておく。 ↑ ← ← ← ↑ ← ← ↑ ← ← ← ↓ ← → ↓ → → → ↑ ↑ ↑ ↓ → → ↓ → → ↓ → → ↓ → → → 変数 I マスの座標(I,J)を右図のように取り 1 2 3 4 . . . 1 B(I,J) = 1 〃 = 0 W(I,J) = 1 〃 U(I,J) ＝1 白マスでないとき Nr 白マス(I,J)から上向きにループ線が出て行くとき〃行かないとき＝0 白マス(I,J)から下向きにループ線が出て行くとき〃行かないとき D(I,J) ＝1 ＝0 白マス(I,J)から左向きにループ線が出て行くとき〃行かないとき L(I,J) ＝1 ＝0 ＝0 黒マスでないときマス(I,J)が白のマスのとき = 0 R(I,J) ＝1 2 J 3 . . . マス(I,J)が黒マスのとき白マス(I,J)から右向きにループ線が出て行くとき〃行かないとき N(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 ３．黒マスをセット B(I,J) = 1 (I,J)は盤面から読み取り (I,J)は盤面から読み取り４．白マスの矢印方向は１つ U(I,J)+D(I,J)+L(I,J)+R(I,J) ≦ 1 (I=1,2….…Nr) (J=1,2….…Nc) (I,J)は白マスのみ５．矢印は合流しない U(I+1,J)+D(I-1,J)+L(I,J-1)+R(I,J+1) ≦ 1 (I=1,2….…Nr) (J=1,2….…Nc) (I,J)は白マスのみ Nc ６．盤面指定の黒矢印 ←のとき →のとき ↑のとき ↓のとき L(I,J)＝ 1 L(I,J+1)＝ R(I,J)＝ 1 R(I,J-1)＝ U(I,J)＝ 1 U(I+1,J)＝ R(I,J)＝ 1 R(I-1,J)＝ (I,J)は黒矢印座標 1 1 1 1 ７．矢印の先に矢印がつながる上）矢の先のマスに風が吹いていないとき U(I,J)≦ U(I-1,J)+L(I-1,J)+R(I-1,J) 右向きの風のとき U(I,J)≦ R(I-1,J) 左向きの風のとき U(I,J)≦ L(I-1,J) (I=1,2….…Nr) (J=1,2….…Nc) 白マスのみ左）矢の先のマスに風が吹いていないとき L(I,J)≦ L(I,J+1)+U(I,J+1)+D(I,J+1) 下向きの風のとき L(I,J)≦ D(I,J+1) 上向きの風のとき L(I,J)≦ L(I,J+1) 下）矢の先のマスに風が吹いていないとき D(I,J)≦ D(I+1,J)+L(I+1,J)+R(I+1,J) 右向きの風のとき D(I,J)≦ R(I+1,J) 左向きの風のとき D(I,J)≦ L(I+1,J) 右）矢の先のマスに風が吹いていないとき R(I,J)≦ R(I,J+1)+U(I,J+1)+D(I,J+1) 下向きの風のとき R(I,J)≦ D(I,J+1) 上向きの風のとき R(I,J)≦ U(I,J+1) ８．矢印は盤から外に出ない U (1,J)＝ 0 D(Nr,J)＝0 L (I,1)＝ 0 R(I,Nc)＝0 (J=1,2,....Nc) (I=1,2,....Nr) 白マスのみ９．黒マスに矢印は付かない B(I,J)+U(I,J)+D(I,J)+L(I,J)+R(I,J)≦ 1 (I,J)は黒マス１０．枠の外に向かう矢印はない U (1,J)＝ 0 D(Nr,J)＝0 L (I,1)＝ 0 R(I,Nc)＝0 (J=1,2,....Nc) (I,J)は白マス (I=1,2,....Nr) １１．矢印は黒マスに向かない B(I,J)+D(I-1,J)≦ 1 B(I,J)+U(I+1,J)≦ 1 B(I,J)+L(I,J+1)≦ 1 B(I,J)+R(I,J-1)≦ 1 (I=1,2….…Nr) (J=1,2….…Nc) (I,J)は黒マス１２．矢印番号付けのスタート番号セット与えられた黒矢印のどれかを採り、座標を(Is,Js)として N(Is,Js)＝1 →のとき N(Is,Js+1)＝2 N(Is,Js)＝1 ←のとき N(Is,Js-1)＝2 N(Is,Js)＝1 ↑のとき N(Is-1,Js)＝2 N(Is,Js)＝1 ↓のとき N(Is+1,Js)＝2 １３．矢印番号付け R(I,J-1) = 1 のとき N(I,J) = N(I,J-1)+1 すなわち N(I,J) ≦ N(I,J-1)+1 N(I,J) ≧ N(I,J-1)+1 であるから、ビッグＭを使って N(I,J) ≦ N(I,J-1)+1+bigM*{1-R(I,J-1)} N(I,J)+bigM*{1-R(I,J-1)} ≧ N(I,J-1)+1 同様に N(I,J) ≦ N(I,J+1)+1+bigM*{1-L(I,J+1)} N(I,J)+bigM*{1-L(I,J+1)} ≧ N(I,J+1)+1 N(I,J) ≦ N(I+1,J)+1+bigM*{1-U(I+1,J)} N(I,J)+bigM*{1-U(I+1,J)} ≧ N(I+1,J)+1 N(I,J) ≦ N(I-1,J)+1+bigM*{1-D(I-1,J)} N(I,J)+bigM*{1-D(I-1,J)} ≧ N(I-1,J)+1 (I=1,2,....Nr) (J=1,2,....Nc) (I,J)≠(Is,Js) 上下界 bounds 変数型 binary B(I,J) W(I,J) (I=1,2….…Nr) (J=1,2….…Nc) L(I,J) D(I,J) R(I,J) U(I,J) general N(I,J) 終端 end (I=1,2….…Nr) 白マスのみ (J= 1,2.…… Nc ) (I=1,2….…Nr) 白マスのみ (J= 1,2.…… Nc )