スラローム http://www.nikoli.co.jp/ja/puzzles/suraromu.htmlより解答例題（パズル紹介） 2 2 4 2 2 4 4 4 ⑤ ⑤ ルール下記条件で、○のマスからスタートして白マスを通過して、このマスに戻るループを描く。 ①線は交差したり、枝分かれしてはいけない。 ②破線を「旗門」と呼び、線は全ての旗門と１回ずつ垂直に交差する。 ③両端が同じ数字で挟まれている旗門と、数字のマスから１つだけ出ている旗門で、端の数字は ○のマスから出た線がその旗門と何番目に交差するかを表わす。上記以外の旗門では、順番は問わない。 ④ルールと関係ないが、○の中の数字は旗門の総数を表わす。タテまたはヨコに連続して並んだ破線は全体で１旗門である。この説明分かり難い。旗門通過順序の数字はこの例題のように単純ではないので要注意。 J → 1 2 I 1 ↓ 2 変数マスの行番号をＩ、列番号をＪとして B(I,J) = 1 = 0 W(I,J) = 1 = 0 L(I,J) ＝1 ＝0 D(I,J) ＝1 ＝0 R(I,J) ＝1 ＝0 U(I,J) ＝1 ＝0 2 3 4 . . . ① 黒マスでいとき旗門には番号を振っておく Nr マス(I,J)が白マスのとき〃白マスでないとき白マス(I,J)が左向き矢印を持つ（次に左マスに進む）とき〃持たないとき白マス(I,J)が下向き矢印を持つとき〃持たないとき白マス(I,J)が右向き矢印を持つとき〃持たないとき白マス(I,J)が上向き矢印を持つとき〃持たないとき ② 3 . . . マス(I,J)が黒マスのとき〃 2 Nc C(I,J,K) = 1 白マス(I,J)が旗門をＫ個通過後のとき = 0 N(I,J) 〃でないときマス通過進行方向矢印に通過順に付けた番号目的関数 minimize x （ダミー）制約式 subject to １．マスは白または黒に塗られるから、 B(I,J)+W(I,J) = 1 (I=1,2….…Nr) (J= 1,2.…… Nc ) ２．与えられた黒マス B(I,J) ＝ 1 ３．マスに付く矢印はどれかの方向１種だから L(I,J)+D(I,J)+R(I,J)+U(I,J) (I=1,2….…Nr) (J= 1,2.…… Nc ) ≦ 1 ≦ 1-B(I,J) ４．黒マスには矢印が付かない L(I,J)+D(I,J)+R(I,J)+U(I,J) (I,Jは盤面の黒マス) ５．矢印は黒マス方向へは向かない、盤面から外へは向かない L(I,J)+B(I,J-1) ≦ 1 D(I,J)+B(I+1,J) ≦ 1 R(I,J)+B(I,J+1) ≦ 1 U(I,J)+B(I-1,J) ≦ 1 L(I,1) ＝ 0 D(Nr,J) ＝ 0 R(I,Nc) ＝ 0 U(1,J) ＝ 0 (I=1,2….…Nr) (J= 1,2.…… Nc ) ６．スタートマスの旗門通過番号＝０、矢印番号＝０とする C(Is,Js,0) = 1 N(Is,Js) = 0 (Is,Jsは盤面○のある座標) ７．矢印は旗門を通過する縦旗門 Σ{D(Ik,Jk)+U(Ik,Jk)} ≧ 1 横旗門 Σ{L(Ik,Jk)+R(Ik,Jk)} ≧ 1 (Ik,Jkは旗門マスの座標) Σは旗門マスが連続するときの和８．旗門と平行な矢印はない縦旗門 U(Ik,Jk)+D(Ik,Jk) ＝ 0 横旗門 L(Ik,Jk)+R(Ik,Jk) ＝ 0 (Ik,Jkは旗門マス座標) ９．矢印の先には矢印の根元が繋がる (I=1,2….…Nr) (J= 1,2.…… Nc ) R(1,J)+U(1,J)+D(1,J) ≧ R(I,J-1) L(1,J)+U(1,J)+D(1,J) ≧ L(I,J+1) U(1,J)+L(1,J)+R(1,J) ≧ U(I+1,J) D(1,J)+L(1,J)+R(1,J) ≧ D(I-1,J) １０．隣マスとの矢印往復禁止 U(1,J)+D(1-1,J) ≦ 1 D(1,J)+U(1+1,J) ≦ 1 (I=1,2….…Nr) (J= 1,2.…… Nc ) L(1,J)+R(1,J-1) ≦ 1 R(1,J)+L(1,J+1) ≦ 1 １１．マスに流入する矢印は１本 U(1+1,J)+D(1-1,J)+R(1,J+1)+L(1,J-1) ≦ (I=1,2….…Nr) (J= 1,2.…… Nc ) 1 １２．マスには旗門通過順番号が付く旗門通過順番号 Nk C (I,J,K)≧ Σ K=0 2 2 2 U(1,J)+L(1,J)+R(1,J)+D(I,J) Nk C (I,J,K)≦ Σ K=0 U(1,J)+L(1,J)+R(1,J)+D(I,J) (I=1,2….…Nr) (J= 1,2.…… Nc ) Nkは総旗門数 2 (I=1,2….…Nr) (J= 1,2.…… Nc ) (K= 0,1.…… N k ) １４．旗門マスでは旗門通過順番号は１増える C(I-1,J,K)-C(I,J,K+1) ≦ 1-D(I-1,J) C(I+1,J,K)-C(I,J,K+1) ≦ 1-U(I+1,J) C(I,J+1,K)-C(I,J,K+1) ≦ 1-L(I,J+1) C(I,J-1,K)-C(I,J,K+1) ≦ 1-R(I,J-1) 2 2 3 1 1 3 3 3 3 1 4 4 4 4 4 4 4 1 1 1 4 ⑤ 0 5 0 0 0 0 5 5 4 １３．旗門マス以外では旗門通過順番号は不変 C(I,J,K)-C(I-1,J,K) ≦ 1-D(I-1,J) C(I,J,K)-C(I+1,J,K) ≦ 1-U(I+1,J) C(I,J,K)-C(I,J+1,K) ≦ 1-L(I,J+1) C(I,J,K)-C(I,J-1,K) ≦ 1-R(I,J-1) 2 2 (I,Jは旗門マス座標) (K= 0,1.…… N k ) １５．通過順番号指定旗門 Σ C(Ik,Jk,K) = 1 １６．矢印番号 (Ik,Jkは旗門マスの座標) Σは連続する旗門マスについての和 Kは盤面指定値 N(I,J)をセット。隣から矢印が入ればマス矢印番号は１増える N(I,J) ≧ N(I,J-1)+1 N(I,J) ≦ N(I,J-1)+1 ｝が R(I,J-1)=1 のときに限り成り立つから Mをbig_M(=Nr*Nc=マスの総数)として N(I,J)+M*｛1-R(I,J-1)｝≧ N(I,J-1)+1 N(I,J) ≦ M*｛1-R(I,J-1)｝+N(I,J-1)+1 (I=1,2….…Nr) (J= 1,2.…… Nc ) N(I,J)+M*｛1-L(I,J+1)｝≧ N(I,J+1)+1 N(I,J) ≦ M*｛1-L(I,J+1)｝+N(I,J+1)+1 N(I,J)+M*｛1-U(I+1,J)｝≧ N(I+1,J)+1 N(I,J) ≦ M*｛1-U(I+1,J)｝+N(I+1,J)+1 N(I,J)+M*｛1-D(I-1,J)｝≧ N(I-1,J)+1 N(I,J) ≦ M*｛1-D(I-1,J)｝+N(I-1,J)+1 １７．矢印番号はＭ−１以下（矢印なしのマスの番号が不定で出力が汚くなるのを防ぐ） N(I,J) ≦ M-1 (I=1,2….…Nr) (J= 1,2.…… Nc ) 上下界 bounds 変数型 binary B(I,J) L(I,J) W(I,J) D(I,J) C(I,J,K) R(I,J) U(I,J) (I=1,2….…Nr) (J=1,2….…Nc) (I=1,2….…Nr) (J=1,2….…Nc) (K=0,1….…Nk) general N(I,J) (I=1,2….…Nr) (J=1,2….…Nc) 終端 end 巡回セールスマン式の順番付けをしているため大きなサイズの問題では、整数計画法が動かなくなる。ただ、パイプリンクに比べると、順番付けするマスの数が半分くらいなので、１０ｘ１０マス程度まで解くことができる。