鉛筆パズルの整数計画法による解法定式化集３． 2015.5.20 改訂 2015.6.20 二訂 2015.6.30 三訂スリザーリンク＊１（www.nikoli.comスリザーリンクのお試し問題）解答例題（お試し問題２より） 1 0 1 1 0 2 2 0 0 1 0 3 3 3 1 1 2 1 2 2 0 1 3 2 0 3 0 1 0 3 3 3 2 3 3 1 2 2 0 1 0 1 1 0 0 1 0 3 3 3 1 1 2 1 2 2 0 1 3 2 0 3 0 1 0 3 3 3 2 3 3 1 ルール＊１のパズルのルール参照のこと。 ①点を繋いで全体が一つの輪になるような線を引いてゆく。 ②数字は、その周りに何本の線を引くかを表す。 ③数字のないところは、まわりに何本の線を引くか自由。 ④線は交差したり、枝分かれしてはならない。スリザーリンクは、上記ルール①の全体が一つの輪になるというところで苦労する。お試し問題２を例題としたのは、＊１のルール説明のサンプルやお試し問題１では、単に線を切れ目無く、交差・枝分かれなく引くだけで全体が繋がってしまい、スリザーリンクの一番苦労する特徴が出ないからである。行番号 I=0 1 2 3 . . Nc 列番号 J=0 1 2 3 . . まずは、切れ目無く、交差・枝分かれなく引くだけだと、どうなるかやってみる。点配列に下図のように行番号、列番号、マス番号を振り、水平線、鉛直線に名前を付ける。マス(I,J) 鉛直線 v(I,J) 水平線 h(I,J) Nr 変数 h(I,J) =1 ,v(I,J)=1 ＝0 〃点間に線を引くとき引かないとき目的関数 minimize （ダミー） x 制約式 subject to １．数字Ｎのあるマスの座標を(In,Jn)として、数字の周りにはＮ本の線を引くから、 h(In-1,Jn)+h(In,Jn)+v(In,Jn-1)+v(In,Jn)=N （数字のあるマスすべてについて座標 (In-1,Jn) など周辺部調整必要）｝２．線は枝分かれしないから、 h(I,J)+h(I,J+1)+v(I,J)+v(I+1,J)≦ 2 (I=0,1….…Nr-1) (J=0,1….…Nc-1) ３．線は繋がっているから、v(I,J)=1であれば、v(I,J)の上端には必ず線があるから h(I-1,J)+h(I-1,J+1)+v(I-1,J)≧ v(I,J) (I=1,2….…Nr) (J=1,2….…Nc-1) v(I,J)下端、h(I,J)左右端についても同様の式が立つ。上下界 bounds 変数型 binary h(I,J) v(I,J) (I=0,1….…Nr) (J=0,1….…Nc) 終端 end 以上の定式化に基づいて解いた結果は、下図のようになる。当然のことながら全体は繋がらない。 1 0 1 1 0 2 2 0 0 1 0 3 3 3 1 1 2 1 2 2 0 1 2 3 3 0 0 1 0 3 3 3 2 3 3 1 そこでh(I,J)、v(I,J)に矢印を付け、矢の先に矢をつなぎ、１から順に番号を振ることにより全体を繋ぐことにする。マスは前ページの図のように黒白に塗り分けておく。追加変数 B(I,J) ＝＝ W(I,J) ＝＝マス(I,J)が黒塗り（線の内側）とき〃外のときマス(I,J)が白塗り（線の外側）とき〃内のとき 1 0 1 0 hL(I,J) ＝＝ vD(I,J) ＝＝ hR(I,J) ＝ 1 0 1 0 1 ＝ 0 vU(I,J) ＝ 1 ＝ 0 格子点をつなぐ矢が左向きのとき〃でないとき格子点をつなぐ矢が下向きのとき〃でないとき格子点をつなぐ矢が右向きのとき〃でないとき格子点をつなぐ矢が上向きのとき〃でないとき K(I,J)＝ M 格子点(I,J)がM番目の点のとき追加制約式４．マスは白マスまたは黒マスである (I=1,2….…Nr) (J=1,2….…Nc) B(I,J)+W(I,J) ＝ 1 v(I,J) ５．v(I,J)=1の線を跨ぐとB(I,J) は０から１に変わるから、 B(I,J)+v(I,J)+B(I,J+1) ≦ B(I,J)+B(I,J+1) ≧ v(I,J) v(J,I)+B(I,J+1) ≧ B(I,J) B(I,J)+v(J,I) ≧ 2 B(I,J+1) ｝｝ h(I,J) B(I,J) また、h(I,J)=1の線を跨ぐとB(I,J) は０から１に変わるから、 B(I,J)+h(I,J)+B(I+1,J) ≦ B(I,J)+B(I+1,J) ≧ h(I,J) h(I,J)+B(I+1,J) ≧ B(I,J) B(I,J)+h(I,J) ≧ B(I+1,J) 2 B(I,J) B(I,J+1) B(I+1,J) (I=0,1….…Nr) (J=0,1….…Nc) ただし、実領域の外周に１層ダミーのマスを設けW(I,J)=1、B(I,J)=0としておく。６．v(I,J)には上下の矢印が付く v(I,J) ＝ vU(I,J)+vD(I,J) (I=0,1….…Nr) (J=0,1….…Nc) ７．h(I,J)には左右の矢印が付く h(I,J) ＝ hL(I,J)+hR(I,J) (I=0,1….…Nr) (J=0,1….…Nc) 2015.6.30 三訂追加解析時間に大きく影響する７A．黒マスは隣接する B(I,J) ≦ B(I,J-1)+B(I,J+1)+B(I-1,J)+B(I+1,J) (J=1,2….…Nc) (I=1,2….…Nr) ８．矢印は黒マス領域を左側に見て進むことにする黒マス左辺には上向き矢印は付かない B(I,J)+vU(I,J-1) ≦ 1 (I=1,2….…Nr) (J=1,2….…Nc) 黒マス右辺には下向き矢印は付かない B(I,J)+vD(I,J) ≦ 1 同様に B(I,J)+vR(I-1,J) ≦ 1 B(I,J)+vL(I,J) ≦ 1 条件７．の定義に注意、hRは辺(I,J)に付く二訂 K(I,J)≧K(I,J-1)+1 だけでよい。増加して行けばよく、１づつである９．矢印付け根の格子点に番号を振って行く必要はない。出発点（わかっているものとし、座標(Is,Js)とする）解析結果は１づつになる。 K(Is,Js)＝ 1 hR(I,J-1)=1のときに限り K(I,J)=K(I,J-1)+1 であるから K(I,J)≦ K(I,J-1)+1 の不等号の大なる方にbigMを付けて K(I,J)≧ K(I,J-1)+1 } K(I,J)≦ K(I,J-1)+1+bigM*{1-hR(I,J-1)} (I=1,2,.....Nr) (J=1,2,.....Nc) ただし、(Is,Js)以外 K(I,J)+bigM*{1-hR(I,J-1)}≧ K(I,J-1)+1 同様にして、 K(I,J)≦ K(I+1,J)+1+bigM*{1-vU(I+1,J)} K(I,J)+bigM*{1-vU(I+1,J)}≧ K(I+1,J)+1 K(I,J)≦ K(I,J+1)+1+bigM*{1-hL(I,J+1)} K(I,J)+bigM*{1-hL(I,J+1)}≧ K(I,J+1)+1 K(I,J)≦ K(I-1,J)+1+bigM*{1-vD(I-1,J)} K(I,J)+bigM*{1-vD(I-1,J)}≧ K(I-1,J)+1 注）bigMとしてはマス数＝Nr*Ncを使っているパズルが多いがスリリンではその２倍ぐらいにしないと不足する。上下界追加 K(I,J)≦bigM (I=0,1….…Nr) (J= 0,1.…… Nc ) 変数型追加 binary B(I,J) W(I,J) (I=0,1….…Nr+1) (J=0,1….…Nc+1) hL(I,J) hR(I,J) (I=0,1….…Nr) (J= 1,2.…… Nc ) vU(I,J) vD(I,J) (I=1,2….…Nr) (J= 0,1.…… Nc ) general K(I,J) (I=0,1….…Nr) (J= 0,1.…… Nc ) 出発点についてループでつながっている点に１から番号を振って行くので、ループをどこかで切断し起点を決めてやらなければならない。そのためには、初めから黒マスになるのが確実なマス一つとその白マスとの境界辺を知っておかなければならない。次のような型がある。１．隅の１、０２．隅の３ 1 0 ３．隅の３、０ 3 注）盤の外枠より外側は白マスと考える。従って外枠マスの０は必ず白マスになる。４．隅の３、３ 3 3 0 3 ５．辺の２、０６．辺の３、０ 2 0 ７．辺の３、０（タテ） 3 0 ８．辺の０、３（タテ） 3 0 0 3 これらの型が一つもなく、出発点が求まらない問題があり、そのときは適当に当たるまで変えてみる。「クリーク」と同じように、出発点を自動探索させるのは解析時間が長くなって使えない。格子点に番号付して全体を繋ぐことにしたので、形式的にはスッキリしたが、解けるのは盤の大きさが１８ｘ１０ぐらいまでで、３６ｘ２０になると、動かなくなる問題も出てくる。黒マスに矢印を付けた旧プログラムも捨てがたいものがある。