ひとりにしてくれ

2014.12.24 改訂ひとりにしてくれ
www.nikoli.comひとりにしてくれのお試し問題
＊１
解答
例題（パズルのルールより）
1
8
6
2
6
7
5
3
1
8
6
2
6
7
5
3
3
1
1
1
8
2
2
2
3
1
1
1
8
2
2
2
8
3
2
4
7
6
5
1
8
3
2
4
7
6
5
1
3
7
5
8
3
3
1
4
3
7
5
8
3
3
1
4
5
4
4
6
7
1
8
2
5
4
4
6
7
1
8
2
7
1
4
3
2
5
3
5
7
1
4
3
2
5
3
5
2
2
8
3
4
4
7
5
2
2
8
3
4
4
7
5
2
2
3
1
4
4
6
5
2
2
3
1
4
4
6
5
ルール
＊１参照のこと
以下の条件に従ってマスを塗りつぶす。
①タテ列でもヨコ列でも、同じ数字があってはいけない。
②タテかヨコに黒マスが連続してはいけない（斜めはよい）。
③白マスは全部繋がっていなければならない。
ひとりにしてくれの白マス領域は全体が繋がり難く、ほんとに泣ける。スリザーリンクで使った、
矢の先に矢を繋ぐ方式で、隣接マスの対向矢印禁止にしてもまだ分断するので、やってみた結果から
勝手に作った禁止条件をずらずらと書き並べた。白マスの全部繋がりは、「へやわけ」方式に変更。
変数
J →
1 2
マスの行番号をＩ、列番号をＪとして
b(I,J) = 1
= 0
w(I,J) = 1
= 0
g(I,J,K) = 1
= 0
マス(I,J)を黒く塗りつぶすとき
〃塗りつぶさないとき
マス(I,J)が白マスのとき
〃 3
4
. . .
I 1
↓ 2
3
.
.
.
Nr
白マスでないとき
マス(I,J)の数字がＫのとき
〃数字がＫでないとき
wF(I,J,K) = 1 マス(I,J)が白マスで且つ数字がＫのとき
〃数字がＫでないとき
= 0
LU(I,J) ＝1 黒マス(I,J)が左上向き矢印を持つ（左上黒マスとカド接触）とき
＝0
〃持たないとき
LD(I,J) ＝1 黒マス(I,J)が左下向き矢印を持つとき
＝0
〃持たないとき
RU(I,J) ＝1 黒マス(I,J)が右上向き矢印を持つとき
＝0
〃持たないとき
RD(I,J) ＝1 黒マス(I,J)が右下向き矢印を持つとき
＝0
〃持たないとき
Nc
目的関数
minimize
（ダミー）
x
制約式
subject to
１．g(I,J,K)をセットする
g(I,J,K)=1
または0を問題のテーブルに合わせてセットする。
２．マスは白または黒に塗られるから、
b(I,J)+w(I,J)
=
1
(I=1,2….…Nr)
(J= 1,2.…… Nc )
３．白マスで数字Ｋのものを
wF(I,J,K)=1とする
g(I,J,K)+w(I,J)-wF(I,J,K)
≦
1
(K=1,2….…M) Mは最大の数字
(I=1,2….…Nr)
(J=1,2….…Nc)
wF(I,J,K) ≦ g(I,J,K)
wF(I,J,K) ≦ w(I,J)
４．１行の数字は１回しか現れないから、
Nc
wF(I,J,K)
Σ
J=1
≦
1
(K=1,2….…M) Mは最大の数字
(I=1,2….…Nr)
５．１列の数字は１回しか現れないから、
Nr
wF(I,J,K)
Σ
I=1
≦
1
(K=1,2….…M) Mは最大の数字
(J=1,2….…Nc)
６．白マスは連続しているから、
w(I-1,J)+w(I,J-1)+w(I+1,J)+w(I,J+1)
≧
w(I,J)
(I=1,2….…Nr)
(J=1,2….…Nc)
７．黒マス２連禁止。
ヨコ
b(I,J)+b(I,J+1)
≦
1
タテ
b(I,J)+b(I+1,J)
≦
1
(I=1,2….…Nr-1)
(J=1,2….…Nc-1)
黒マスがこの配置なら
どちらかの矢印が付く
８．黒マスに矢印をセットする
b(I,J)+b(I-1,J-1)-LU(I,J)-RD(I-1,J-1)≦ 1 (I=1,2….…Nr)
b(I,J)+b(I+1,J-1)-LD(I,J)-RU(I+1,J-1)≦ 1 (J=1,2….…Nc)
b(I,J)+b(I-1,J+1)-RU(I,J)-LD(I-1,J+1)≦ 1
b(I,J)+b(I+1,J+1)-RD(I,J)-LU(I+1,J+1)≦ 1
９．矢印は白マスに向かない
LU(I,J)+w(I-1,J-1) ≦ 1
LD(I,J)+w(I+1,J-1) ≦ 1
RU(I,J)+w(I-1,J+1) ≦ 1
RD(I,J)+w(I+1,J+1) ≦ 1
(I=1,2,....Nr)
(J=1,2,....Nc)
１０．白マスに矢印は付かない
LU(I,J)+w(I,J) ≦ 1
LD(I,J)+w(I,J) ≦ 1
(I=1,2,....Nr)
(J=1,2,....Nc)
RU(I,J)+w(I,J) ≦ 1
RD(I,J)+w(I,J) ≦ 1
１１．矢印は外周から外へは向かない
LU(1,J)+RU(1,J) ＝ 0
LD(Nr,J)+RD(Nr,J) ＝ 0
LU(1,J)+LD(1,J) ＝ 0
RU(I,Nc)+RD(I,Nc) ＝ 0
(J=1,2….…Nc)
(I=1,2….…Nr)
１２．外周では矢印は内向き
b(1,J)+b(2,J-1)-LD(1,J)≦ 1
(J=1,2….…Nc)
b(1,J)+b(2,J+1)-RD(1,J)≦ 1
b(Nr,J)+b(Nr-1,J-1)-LU(Nr,J)≦ 1
b(Nr,J)+b(Nr-1,J+1)-RU(Nr,J)≦ 1
b(I,1)+b(I-1,2)-RU(I,1)≦ 1
(I=1,2….…Nr)
b(I,1)+b(I+1,2)-RD(I,1)≦ 1
b(I,Nc)+b(I,Nc-1)-LU(I,Nc)≦ 1
b(I,Nc)+b(I,Nc-1)-RU(I,Nc)≦ 1
上下界
bounds
変数型
binary
b(I,J) w(I,J)
(I=1,2….…Nr)
(J=1,2….…Nc)
wF(I,J,K)
(K=1,2….…M)
(I=1,2….…Nr)
(J=1,2….…Nc)
LU(I,J) LD(I,J) RU(I,J) RD(I,J)
(I=1,2….…Nr)
(J= 1,2.…… Nc )
終端
end
白マスつなぎに使った黒マス矢印の解析結果を示す。
1
8
6
2
6
7
5
3
3
1
1
1
8
2
2
2
8
3
2
4
7
6
5
1
3
7
5
8
3
3
1
4
5
4
4
6
7
1
8
2
7
1
4
3
2
5
3
5
2
2
8
3
4
4
7
5
2
2
3
1
4
4
6
5

Download Report