天体ショー - 鉛筆パズルの整数計画法による解法定式化集

鉛筆パズルの整数計画法による解法定式化集５２．
天体ショー
http://www.nikoli.co.jp/ja/puzzles/astronomical_show.html
例題（ニコリのパズル紹介より）
解答
ルール
マスの境界に太線を引いて、盤面をいくつかのブロックにに分割する。
①すべてのブロックが星（○か●）を一つずつ含み、しかも星を中心とした点対称の図形
になるようにしなければならない。
②●の入ったブロックは、すべて黒くぬりつぶす。
○と●は、パズルを解く上では区別をする必要がない。ルール②は正解を求めることとは
関係がないので、ルールではない。
マスの行番号をＩ、列番号をＪとし、星にも番号を振っておく。星はマスの境界線上に置かれた
ものがあるので、星用の座標(II,JJ)も用意する。
JJ → 1
II 1
↓ 2
I 1
↓
3
2
3
.
.
.
2*Nr-1
.
.
.
Nr
2
3
J →
1
2
2*Nc-1
3
①
. . . ②Nc ③
星の入ったマス、或いは境界線上に星があるマスは
その星の所属マスとなるので、所属を選択できる自由な
マスは意外と数が少なく、この例題では、左図で灰色に
塗ったマスだけである。
各星の、これらの灰色マスの点対称の位置を調べて、
点対称マスが全て盤の外または、他の星の領域上に重なって
しまい、灰色マスと重なるものが一つもないとき、その星
のブロックは拡張の可能性がなく、境界は最小領域に確定
してしまう。
盤の４隅、辺に並んだ星などは、調べるまでもなく、
単独マスブロックとなる。
境界が決定してしまう星は、事前に調べておく。
この例題の場合、左図の赤描きの星が該当し、その境界も
図のように決定する。
この例では、整数計画法に残された仕事が殆どなくなって
いるが、普通の問題では、こうはならない。
変数
S(I,J,K) = 1
= 0
マス(I,J)が星Ｋのブロックに所属するとき
〃しないとき
目的関数
minimize
（ダミー）
x
制約式
subject to
１．マスはどれかの星に属する
Ns
S(I,J,K)＝
Σ
K=1
1
(I=1,2,....Nr)
(J=1,2,....Nc)
Nsは星の総数
２．星のあるマスはその星のブロックに所属する
S(I,J,K)＝ 1 (I=1,2,....Nr)
(J=1,2,....Nc)
(K=1,2,....Ns)
(I,J)は星Ｋのあるマスまたは
星が掛かっているマスの座標
３．点対称自由マスを持たない星Ｋのブロックは領域が確定する
S(I,J,K)＝ 0
(K=1,2,....Ns) (I,J)は星Ｋの最小領域以外のマス
４．マス(I,J)がＫの星に属すればその点対称位置のマスもＫに属する
S(I,J,K) ≦ S(II,JJ,K) (K=1,2,....Ns)
(I,J)は自由マス座標、(II,JJ)はその星 Kに関する点対称位置
５．自由マスは単独ブロックにならない
S(I,J,K) ≦ S(I-1,J,K)+S(I+1,J,K)+S(I,J+1,K)+S(I-1,J,K)
(I,J)は自由マス座標
(K=1,2,....Ns)
６．自由マスは２マスブロックにならない
タテ
S(I,J,K)+S(I+1,J,K)-1 ≦ S(I-1,J,K)+S(I,J-1,K)+S(I+1,J-1,K)+S(I+2,J,K)
+S(I+1,J+1,K)+S(I,J+1,K)
ヨコ
S(I,J,K)+S(I,J+1,K)-1 ≦ S(I,J-1,K)+S(I-1,J,K)+S(I-1,J+1,K)+S(I,J+2,K)
+S(I+1,J+1,K)+S(I+1,J,K)
(K=1,2,....Ns)
(I,J)は自由マス座標
７．自由マスは３マスＬ型ブロックにならない
S(I,J,K)+S(I+1,J,K)+S(I+1,J+1,K)-2 ≦ S(I-1,J,K)+S(I,J-1,K)+S(I+2,J,K)+S(I+2,J+1,K)
+S(I+1,J+2,K)+S(I+1,J+2,K)+S(I,J+1,K)
S(I,J+1,K)+S(I+1,J,K)+S(I+1,J+1,K)-2 ≦ S(I,J,K)+S(I+1,J-1,K)+S(I+2,J,K)+S(I+2,J+1,K)
+S(I+1,J+2,K)+S(I,J+2,K)+S(I-1,J+1,K)
S(I,J,K)+S(I+1,J,K)+S(I,J+1,K)-2 ≦ S(I-1,J+1,K)+S(I-1,J,K)+S(I,J-1,K)+S(I+1,J-1,K)
+S(I+2,J,K)+S(I,J+2,K)+S(I+1,J+1,K)
S(I,J,K)+S(I,J+1,K)+S(I+1,J+1,K)-2 ≦ S(I-1,J+1,K)+S(I-1,J,K)+S(I,J-1,K)+S(I+2,J+1,K)
+S(I,J+2,K)+S(I+1,J+2,K)+S(I+1,J,K)
(K=1,2,....Ns)
(I,J)は自由マス座標
上下界
bounds
変数型
binary
S(I,J,K)
(I=1,2….…Nr)
(J=1,2….…Nc)
(K=1,2….…Ns)
終端
end
本来、一つの星に所属するマスは繋がっている、という条件式を書くべきであるが、サボって
５、６、７のような条件で誤魔化した。その代わり解析は非常に早く、大きなサイズの問題も
一瞬で終わる。
参考
Excel VBAで問題を解く人のために、星の図形座標を読み取る部分のコードを示す。
星をExcelの図形として扱うのは面倒で、単に問題が解ければよいのであれば、境界線上の星は
「下●」「右○」「角○」などとしてセル内の入力文字として読み込む方が楽であろう。
Dim X As Single, Y As Single, Cw As Single, Rh As Single, MH As Single
Dim Nmark As Integer, markI(100) As Integer, markJ(100) As Integer, markC(100) As Integer
'
星座標読み込み
ActiveSheet.Range("A1").Select
Rh = Selection.RowHeight
Cw = Selection.ColumnWidth * 7
ActiveSheet.Shapes.SelectAll
KK = Selection.Count
Nmark = 0
For K = 1 To KK
If Left(Selection.Item(K).Name, 13) <> "CommandButton" Then
X = Selection.Item(K).Left
Y = Selection.Item(K).Top
MH = Selection.Item(K).Height
Nmark = Nmark + 1
markI(Nmark) = (Y + MH / 2) / Rh * 2
markJ(Nmark) = (X + MH / 2) / Cw * 2
markC(Nmark) = Selection.Item(K).ShapeRange.Fill.Visible
End If
Next K
'
ActiveSheet.Range("A1").Select
点対称マスの座標
マスのマス座標を(I,J)、星の星座標を(Is,Js)とするとき
この星に関する点対称マスのマス座標(Im,Jm)は
Im = Is - I + 1
Jm = Js - J + 1

Download Report