タイルペイント

タイルペイント
http://www.nikoli.co.jp/ja/puzzles/tile_paint,html
例題 (ニコリのパズル紹介より)
2
1
4
1
解答
1
1
1
2
2
3
3
2
2
4
1
2
ルール
①盤面上にある、太線で区切られた部分(タイルと呼ぶ)のいくつかを黒く塗る。
②盤面の数字は、その右あるいは下の、外周か次の斜線のマスまでの区切られた一列のうちで、
黒く塗られるマスの数を表す。
③どのタイルも、すべてのマスを塗るか、すべてのマスを塗らずにおくかのどちらかにする。
タイルの一部のマスだけを塗ってはいけない。
注)②で示されているように、数は少ないが盤面のまん中付近にも\と数字を書いたマスのある
問題が存在する。
マスの行番号をI、列番号をJとし、タイルに番号を振り、マス座標との対応を取った表を用意する。
J →
1
2
3
. . . Nc
I 1
↓
1
2
3
4
2
5
2
6
6
3
7
8
8
9
10 11 12
9
.
.
.
Nr
変数
B(I,J) = 1
= 0
マス(I,J)を黒く塗るとき
〃 塗らないとき
W(I,J) = 1
= 0
マス(I,J)を黒く塗らないとき
〃 塗るとき
TB(K) =
=
TW(K) =
=
タイル(K)を黒く塗るとき
〃 塗らないとき
1
0
1
0
タイル(K)を黒く塗らないとき
〃 塗るとき
目的関数
minimize
(ダミー)
x
制約式
subject to
1.マスは白または黒である
B(I,J)+W(I,J) = 1
(I=1,2,....Nr)
(J=1,2,....Nc)
2.斜線マスは白マスである
W(I,J) = 1
(I,J)は盤中の斜線マス(もしあれば)
3.タイルは白または黒である
(K=1,2,....Nt)
TB(K)+TW(K) = 1
Ntはタイル総数
4.タイルKが黒のときの黒マスB(I,J)
TB(K) ≦ B(I,J)
(K=1,2,....Nt)
(I,J)はタイルとマス座標との対応表から
5.タイルKが白のときの白マスW(I,J)
TW(K) ≦ W(I,J)
(K=1,2,....Nt)
(I,J)はタイルとマス座標との対応表から
6.タテ方向黒マスの数
K
B(I,J)=Nf
Σ
I=1
(J=1,2,....Nc)
KはNrまたは斜線マスI座標、Nfは盤面指定数字
7.ヨコ方向黒マスの数
K
B(I,J)=Nf
Σ
J=1
(I=1,2,....Nr)
KはNcまたは斜線マスJ座標、Nfは盤面指定数字
上下界
bounds
変数型
binary
B(I,J) W(I,J)
(I=1,2….…Nr)
(J=1,2….…Nc)
TB(K) TW(K)
(K=1,2….…Nt)
general
終端
end