四角に切れ

四角に切れ
www.nikoli.com四角に切れのお試し問題
＊１
例題（パズルのルールより）
9
8
4 2
2
4
解答
4 2
2
5
6 8
4
4
6
5
6 8
4
7
6
7
6
4 4
3
9
8
4 4
3
4
4 2
4
4 2
6
8
8
ルール
＊１参照のこと
盤面を長方形か正方形の区画に切り分けてゆく。
①各区画には必ず一つの数字が入る。
②切り分けた区画には数字と同じ数のマスがなければならない。
③解き終わったらマスは余らない。（数字の合計＝マスの総数になっている。）
数字６ならば、１ｘ６、２ｘ３のようにマスを纏めたコマを用意し、ジグゾーパズルのように
埋め込んで行く。整数計画法よりも、それ以前の準備作業の方が手間が掛かる。
数字には左上から順に番号を振って区画番号とする。
J →
1 2
変数
I 1
↓ 2
マスの行番号をＩ、列番号をＪとして
c(I,J,K) = 1
= 0
マス (I,J) が区画Ｋのとき
〃でないとき
3
.
.
.
Nr
p(K,L,M) = 1
= 0
姿勢と数字位置
数字２のとき
姿勢１
姿勢２
区画Ｋのコマが姿勢Ｌ、数字位置Ｍのとき
〃でないとき
数字位置１
2
数字位置２
数字位置１
2
2
数字位置２
2
3
4
. . .
Nc
数字４のとき
姿勢１
①②③④
①
②
③
④
姿勢２
姿勢３
①∼④は４の数字が来る数字位置
① ②
③④
その他問題に応じて適当な数まで決めておく。
目的関数
minimize
（ダミー）
x
制約式
subject to
１．マスはどれかの区画に属するから、
Nk
c(I,J,K)
Σ
K=1
=
1
(I=1,2….…Nr)
(J= 1,2.…… Nc )
Nkは総区画数
ただし、区画Ｋの存在可能な(I,J)の範囲は
調べておき、c(I,J,K)はその範囲のマスのみ
とする。（変数があまり多くならないように）
２．区画Ｋに書かれた数字をＳとすると、c(I,J,K)の区画Ｋ内の合計はＳだから
Nr Nc
Σ
Σc(I,J,K)
I=1 J=1
=
S
(K=1,2….…Nk)
３．コマはどれかの姿勢、数字位置をとるから、
NL NM
Σ
Σp(K,L,M)
L=1 M=1
=
(K=1,2….…Nk)
1
NLは区画Ｋの数字の姿勢数
NMは区画Ｋの数字の数字位置数
４．p(K,L,M)=1のときc(I,J,K)=1となるマスをセットする
区画Ｋの数字座標を(In,Jn)とすると
c(In±I,Jn±J,K)
≧
p(K,L,M)
(K=1,2….…Nk)
(L=1,2….…NL)
(M=1,2….…NM)
(IはL,Mで調整)
(JはL,Mで調整)
いいかげんなかきかたであるが
実際は数字ごとに相当ややこしい
上下界
bounds
変数型
binary
c(I,J,K)
(K=1,2….…Nk)
(I=1,2….…Nr)
(J=1,2….…Nc)
p(K,L,M)
(K=1,2….…Nk)
(L=1,2….…NL)
(M=1,2….…NM)
終端
end

Download Report