1. No category

アイスバーン
http://www.nikoli.co.jp/ja/puzzles/eisbahn.html
例題 （ニコリのパズル紹介より）
←
IN →
←
IN →
解答
↑
↑
→ OUT
→
→
→ OUT
ルール
以下の条件に従って、INから入ってOUTに出るように、盤面に分岐のない線を引く。
①線はマスの中央を通るようにタテ・ヨコに引く。
②灰色のマスをアイスバーンと呼び、タテ・ヨコに繋がっている灰色のマスは、全て一つの
アイスバーンとする。
③線はそれぞれのアイスバーンを少なくとも１回ずつ通らなければならない。
④線はアイスバーンの上では曲げられないが、アイスバーンの上でのみ交差させることができる。
⑤矢印で結ばれた２マスには必ず線を通さなくてはならず、方向は連結線がINからOUTに向う方向
とする。
マスの行番号をＩ、列番号をＪとし、マス境界の矢印は手前のマス所属の、出る方向矢印と考える。
J →
1
I 1
↓
2
3
. . .
Nc
←
→
2
↑
3
.
.
.
Nr
→
→
アイスバーンに番号を振り、マス座標との対応を取った表を用意する。
１ １
２
３
４ ４
変数
R(I,J) = 1
= 0
線がマス(I,J)から右側のマスに繋がるとき
〃 繋がらないとき
L(I,J) = 1
= 0
線がマス(I,J)から左側のマスに繋がるとき
〃 繋がらないとき
U(I,J) = 1
= 0
線がマス(I,J)から上側のマスに繋がるとき
〃 繋がらないとき
線がマス(I,J)から下側のマスに繋がるとき
〃 繋がらないとき
D(I,J) = 1
= 0
Nx；行方向に付けた矢印順番号
Ny；列方向に付けた矢印順番号
Nx,Nyは原則１づつ上がるが、アイスバーンで交差するとき、Nxは上がるが、Nyは上がらず
前の番号を維持することにする。（パイプリンクの立体交差と同じ扱い）
目的関数
minimize
x
（ダミー）
制約式
subject to
１．盤面既定矢印
L(I,J)
R(I,J)
U(I,J)
D(I,J)
＝
＝
＝
＝
1
1
1
1
(I,Jは盤面矢印の
根元側マス座標)
２．アイスバーン以外ではマスから出る矢印は１種である
L(I,J)+R(I,J)+U(I,J)+D(I,J) ≦ 1
(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)
４．アイスバーン以外ではマスに入る矢印は１種である
L(I,J+1)+R(I,J-1)+U(I+1,J)+D(I-1,J) ≦ 1
(I=1,2,....Nr)
(J=1,2,....Nc)
ただしアイスバーン以外
５．アイスバーンのマスでは矢印が突き抜ける
L(I,J+1)
R(I,J-1)
U(I-1,J)
D(I+1,J)
≦
≦
≦
≦
L(I,J)
R(I,J)
U(I,J)
D(I,J)
(I=1,2,....Nr)
(J=1,2,....Nc)
ただしアイスバーンのマスのみ
６．矢印は盤から外に出ない
U (1,J)＝ 0
D(Nr,J)＝0
L (I,1)＝ 0
R(I,Nc)＝0
(J=1,2,....Nc)
(I=1,2,....Nr)
ただしOUTの矢印マスは除く
７．矢印はすべてのアイスバーンを通る
Nr Nc
Σ {L(I,J)+R(I,J)+U(I,J)+D(I,J)}≧ 1
Σ
I=1 J=1
(K=1,2,....Ni)
Niはアイスバーンの総数
Σはアイスバーン番号Kに対応する
部分の和
８．矢印のスタート番号
(Iin,Jin)はINの矢印の座標
Nx(Iin,Jin) = 1
Nx(Iin,Jin+1) = 2 左からINのとき
Nx(Iin,Jin-1) = 2 右からINのとき
上からINのとき
Ny(Iin,Jin) = 1
Ny(Iin,Jin+1) = 2
注）縦方向矢印番号は、アイスバーンで横方向矢印と交差
するとき付番規則が変わるので、上からアイスバーンに
INする問題では、この式は成り立たない。プログラムを
変えるか、問題を90度回転させて入力する必要がある。
９．ヨコ方向矢印番号付番
R(I,J-1) = 1 のとき
Nx(I,J) = Nx(I,J-1)+1 すなわち
Nx(I,J) ≦ Nx(I,J-1)+1
Nx(I,J) ≧ Nx(I,J-1)+1 であるから、ビッグＭを使って
Nx(I,J) ≦ Nx(I,J-1)+1+bigM*{1-R(I,J-1)}
Nx(I,J)+bigM*{1-R(I,J-1)} ≧ Nx(I,J-1)+1
同様に
Nx(I,J) ≦ Nx(I,J+1)+1+bigM*{1-L(I,J+1)}
Nx(I,J)+bigM*{1-R(I,J+1)} ≧ Nx(I,J+1)+1
(I=1,2,....Nr)
(J=1,2,....Nc)
１０．タテ方向矢印番号付番
D(I-1,J) = 1 のとき、R(I,J)=1 または L(I,J)=1のときは
Ny(I,J) = Ny(I,J-1)+1
の最後の１を加えないので
であるから、ビッグＭを使って
Ny(I,J) = Ny(I,J-1)+1-R(I,J)-L(I,J)
Ny(I,J) ≦ Ny(I+1,J)+1-R(I,J)-L(I,J)+bigM*{1-D(I+1,J)}
Ny(I,J)+bigM*{1-D(I+1,J)} ≧ Ny(I+1,J)+1-R(I,J)-L(I,J)
同様に
Ny(I,J) ≦ Ny(I-1,J)+1-R(I,J)-L(I,J)+bigM*{1-U(I-1,J)}
Ny(I,J)+bigM*{1-U(I-1,J)} ≧ Ny(I-1,J)+1-R(I,J)-L(I,J)
１１．アイスバーン以外では Nx=Ny
Nx(I,J) ≦ Ny(I,J)
(I=1,2,....Nr)
(J=1,2,....Nc)
ただし(I,J)はアイスバーン以外
(I=1,2,....Nr)
(J=1,2,....Nc)
上下界
bounds
変数型
binary
L(I,J) R(I,J)
U(I,J) D(I,J)
(I=1,2….…Nr)
(J=1,2….…Nc)
general
Nx Ny
終端
end
アイスバーンは、番号付けをしているが、整数計画法の解析時間が短く、大きな問題でもすぐ解ける。