1. No category

ウォールロジック
（整数計画法によるパズル解法
例題 岡本吉央 第９章より）
解答
2
1
2
2
1
1
1
1
2
3
2
3
2
1
1
1
2
4
2
4
1
4
1
4
ルール
以下の条件に従って各数字から線を引く。
①数字が記入されているマスからその数字の数だけ縦と横に線を引く。
②一つのマスには１本の線しか引くことができない。
③数字が記入されているマスには線を引くことができない。
計算上の解答は線を引く代わりにマスに記号を入れた下図のようなものとする。
4
D
D
1
D
L
R
4
D
D
1
L
R
R
2
D
R
3
1
R
R
1
D
R
R
2
D
D
1
D
U
U
2
U
U
2
U
上に向かって引いた線
D
下に向かって引いた線
L
左に向かって引いた線
R
右に向かって引いた線
変数
マスの行番号をＩ、列番号をＪとして
U(I,J) = 1
= 0
D(I,J) = 1
= 0
マス(I,J)に上に向かう線が入るとき
〃 入らないとき
マス(I,J)に下に向かう線が入るとき
〃 入らないとき
J →
1 2
I 1
↓ 2
3
.
.
.
Nr
L(I,J) = 1
= 0
R(I,J) = 1
= 0
マス(I,J)に左に向かう線が入るとき
〃 入らないとき
マス(I,J)に右に向かう線が入るとき
〃 入らないとき
3
4
. . .
Nc
目的関数
minimize
（ダミー）
x
制約式
subject to
１．マスにはU,D,L,Rのどれかの記号が入るから
U(I,J)+D(I,J)+L(I,J)+R(I,J)＝ 1
(I=1,2,....Nr)
(J=1,2,....Nc)
ただし数字のない空白マスのみ
２．数字Ｎの入っているマスを(In,Jn)とすると、U,D,L,Rが書き込み可能なマスが周りに
Ｎ個以上ないといけないから、
Mu
Md
Ml
Mr
U(In-I,Jn) ＋ Σ D(In+I,Jn) ＋ Σ L(In,Jn-J) ＋ Σ R(In,Jn+J)
Σ
I=1
I=1
J=1
J=1
≧ N （全数字マスに対し）
Σの範囲はそれぞれの方向で隣の数字または外枠につっかえるまで、M≦Nである。
３．数字に近い方のマスに、同一記号が入っていないとその先の記号が入れられないから
U(In-I,Jn) ≧
U(In-I-1,Jn)
D(In+I,Jn) ≧ D(In+I+1,Jn)
L(In,Jn-J) ≧ L(In,Jn-J-1)
R(In,Jn+J) ≧ R(In,Jn+J+1)
上下界
bounds
変数型
binary
U(I,J)
D(I,J)
L(I,J)
R(I,J)
終端
end
(I=1,2,...Nr)
(J=1,2,...Nc)
ただし数字のない空白マスのみ
（全数字マスに対し）
I,J は２．と同一範囲