ヘルゴルフ

ヘルゴルフ
http://www.nikoli.co.jp/ja/puzzles/herugolf.html
解答
例題（ニコリのパズル紹介より）
４
４
Ｈ
Ｈ
Ｈ
Ｈ
Ｈ
２
２
２
Ｈ
２
ルール
以下の条件に従って○（ボール）をＨ（ホール）のマスまで移動する。
①すべてのＨのマスにボールが一つづつ運ばれる。
②各回の○の移動は矢印で表す。矢印の線が他の丸やＨのマスを通過したり、線どうしが
交差したり重なってはいけない。
③１回の移動で、○はタテかヨコにまっすぐ、丸の中の数字の分だけマスを動く。
１回の移動が終わると丸の数字は１減り、また移動することがでる。移動の方向は変わってもよい。
数字が０になったボールや、Ｈのマスに停止したボールはそれ以上移動できない。
④○が盤面の外に出たり(OB)､灰色のマス(池)で停止したりするような移動はできない。
ボール１
ボール２
変数
マスの行番号をＩ、列番号をＪとし、与えられた○にも番号を振っておく。
C(I,J,K) = 1
= 0
マス(I,J)にＫ番目のボールが通るとき
〃通らないとき
マス(I,J)がホールのとき
〃でないとき
H(I,J) = 1
= 0
I 1
↓ 2
J →
1 2
4
3
.
.
.
Nr
sL(K,L) = 1
Ｋ番目のボールのＬストローク目が左方向のとき
〃でないとき
= 0
sR(K,L) = 1
Ｋ番目のボールのＬストローク目が右方向のとき
〃でないとき
= 0
sU(K,L) = 1
Ｋ番目のボールのＬストローク目が上方向のとき
〃でないとき
= 0
sD(K,L) = 1
Ｋ番目のボールのＬストローク目が下方向のとき
〃でないとき
= 0
S(I,J,K,L) = 1 マス(I,J)がＫ番目のボールのＬストローク目の終点のとき
= 0
〃でないとき
目的関数
minimize
x
（ダミー）
制約式
subject to
１．ホール位置設定
H (I,J)=1 または H(I,J)=0
(I,Jは盤面読み取り)
H
2
3
4
. . .
Nc
２．マスを通過するボールはどれか１個以下だから
Nb
C (I,J,K)≦ 1
Σ
K=1
(I=1,2,....Nr) Nbはボールの総数
(J=1,2,....Nc)
ただし初期ボールのあるマスではC(I,J,K)=1、C(I,J,KK)=0 (KKはK以外のとき)
３．ボールの飛ぶ方向は１方向だから
sL(K,L)+sD(K,L)+sR(K,L)+sU(K,L)≦ 1
(K=1,2,....Nb)
(L=0,1,....Ns(K)-1)
Ns(K)はボールのストローク数
（盤面丸の中の数値）
４．最初のストロークは必ずある
sL(K,0)+sD(K,0)+sR(K,0)+sU(K,0)≧ 1
５．S(I,J,K,L)の初期値S(I,J,K,0)をセット
初期ボール位置に対し
S(I,J,K,0)=1
S(I,J,K,L)=0
(L=1,....Ns(K))
(K=1,2,....Nb)
(I,Jは初期ボール位置）
初期ボール位置以外ではストローク違いが同一マスには来ないから
S(I,J,K,L)+S(I,J,K,LL)≦ 1 (K=1,2,....Nb)
(I=1,2,....Nr)
(LL＞L)
(I,Jは初期ボール位置以外）
(J=1,2,....Nc)
６．マス(I,J)には(K,L)の異なるボールがくるから
Nr
Nc
(K=1,2,....Nb)
(L=0,1,....Ns(K))
Σ
Σ S(I,J,K,L)≦ 1
I=1 J=1
７．ボールが盤から飛び出さないための方向制限
sL(K,L)+S(I,J,K,L)≦
sR(K,L)+S(I,J,K,L)≦
sU(K,L)+S(I,J,K,L)≦
sD(K,L)+S(I,J,K,L)≦
1
1
1
1
(J≦Ns(K)-L)
(J＞Nc-(Ns(K)-L))
(I≦Ns(K)-L)
(I＞Nr-(Ns(K)-L))
(K=1,2,....Nb)
(L=0,1,....Ns(K))
(I=1,2,....Nr)
(J=1,2,....Nc)
７．S(I,J,K,L)は池には来ない
(K=1,2,....Nb)
S(I,J,K,L)=0
(L=0,1,....Ns(K))
(I,Jは全ての池のマス）
８．マス(I,J)がホールならば、S(I,J,K,L)のどれかが来る
Nb
Ns(K)
Σ
Σ S(I,J,K,L)≧ 1
K=1 L=1
(I,Jは全てのホールマス）
９．S(I,J,K,L)=1でマス(I,J)がホールでなければストローク矢印が付く
S(I,J,K,L)-｛H(I,J)+sL(K,L)+sD(K,L)+sR(K,L)+SU(K,L)｝≦ 0
(K=1,2,....Nb)
(L=1,2,....Ns(K)-1)
(I=1,2,....Nr)
(J=1,2,....Nc)
１０．S(I,J,K,L)=1でマス(I,J)がホールならばＬより先のストローク矢印はない
S(I,J,K,L)+｛sL(K,LL)+sD(K,LL)+sR(K,LL)+SU(K,LL)｝≦ 1
(LL＞L)
(K=1,2,....Nb)
(L=1,2,....Ns(K)-1)
(I,Jは全てのホールマス）
１１．ストローク矢印がなければ S(I,J,K,L)=0
S(I,J,K,L)-｛sL(K,LL)+sD(K,LL)+sR(K,LL)+SU(K,LL)｝≦ 0
(LL＝L-1)
(K=1,2,....Nb)
(L=1,2,....Ns(K))
(I=1,2,....Nr)
(J=1,2,....Nc)
１２．ストローク矢印の逆戻り禁止
sL(K,L)+sR(K,L+1)≦
sR(K,L)+sL(K,L+1)≦
sU(K,L)+sD(K,L+1)≦
sD(K,L)+sU(K,L+1)≦
1
1
1
1
(K=1,2,....Nb)
(L=0,1,....Ns(K)-1)
１３．ストロークによる S(I,J,K,L)位置の移動
S(I,J,K,L)=1 で sL(K,L)=1 のとき S(I,JJ,K,L+1)=1であるから
ただし JJ=J-(Ns(K)-L) :Ｌストローク目のマス移動
sL(K,L)+S(I,J,K,L)-S(I,JJ,K,L+1)≦ 1
また移動途中のマスはＫ番ボールの通過マスになるから
sL(K,L)+S(I,J,K,L)-C(I,JJJ,K)≦ 1
ただし JJJ=J-1∼J-(Ns(K)-L)
同様にして
sR(K,L)+S(I,J,K,L)-S(I,JJ,K,L+1)≦ 1
JJ=J+(Ns(K)-L)
sR(K,L)+S(I,J,K,L)-C(I,JJJ,K)≦ 1
JJJ=J+1∼J+(Ns(K)-L)
sU(K,L)+S(I,J,K,L)-S(II,J,K,L+1)≦ 1
II=I-(Ns(K)-L)
sU(K,L)+S(I,J,K,L)-C(III,J,K)≦ 1
III=I-1∼I-(Ns(K)-L)
sD(K,L)+S(I,J,K,L)-S(II,J,K,L+1)≦ 1
II=I+(Ns(K)-L)
sD(K,L)+S(I,J,K,L)-C(III,J,K)≦ 1
III=I+1∼I+(Ns(K)-L)
上下界
bounds
変数型
binary
H(I,J)
(I=1,2….…Nr)
(J=1,2….…Nc)
C(I,J,K)
(K=1,2….…Nb)
(I=1,2….…Nr)
(J=1,2….…Nc)
sL(K,L) sR(K,L) sU(K,L) sD(K,L)
S(I,J,K,L)
(K=1,2….…Nb)
(L=0,1….…Ns(K))
(I=1,2….…Nr)
(J=1,2….…Nc)
(K=1,2….…Nb)
(L=0,1….…Ns(K))
終端
end
整数計画法 scip の read solution ファイルから、sL,sR,sU,sDを読んで解とする。
C(I,J,K)はボールが通過しなかったマスに、不定のボール番号が付いて見難い。
solution ファイルを読んでExcel Sheetに矢印を描くVBAプログラムリストを次ページに添付する。
ただし、これまでの説明では、配列の変数名がsL(3,2)などとなっているが、実際のプログラムでは
sL3_2として出力されている。
Private Sub CommandButton3_Click()
Dim TextLine As String
Dim I As Integer, J As Integer, K As Integer, L1 As Integer
Dim Nr As Integer, Nc As Integer, Length As Integer
Dim Crow As Integer, Ccol As Integer, Cgrp As Integer
Dim Ret As Variant, lastLine As Integer, lastCol As Integer
Dim Nball As Integer, BallHit(20) As Integer
Dim Dij(20, 20) As String * 1, BallI(20) As Integer, BallJ(20) As Integer
Dim Ar As String * 1, Ball As Integer, Stroke As Integer
Dim ScX As Integer, ScY As Integer, X0 As Integer, Y0 As Integer
'
ChDrive Left(Application.ThisWorkbook.Path, 1)
ChDir Application.ThisWorkbook.Path
'
ScX = 27.2
エクセルシートの列幅、行高さに合わせ調節しないとずれる。
ScY = 27.2
'
' find Input Range
For I = 1 To 20
If Cells(I, 1).Borders(xlEdgeBottom).LineStyle = 1 Then
Nr = I
End If
Next I
'
For J = 1 To 20
If Cells(1, J).Borders(xlEdgeBottom).LineStyle = 1 Then
Nc = J
End If
Next J
Debug.Print "Nr=", Nr
Debug.Print "Nc=", Nc
'
' Read Ball position
Nball = 0
For I = 1 To Nr
For J = 1 To Nc
If IsNumeric(Cells(I, J)) = False Then
ElseIf IsEmpty(Cells(I, J)) = False Then
Nball = Nball + 1
BallI(Nball) = I
BallJ(Nball) = J
BallHit(Nball) = Cells(I, J).Value
Dij(I, J) = "B"
End If
Next J
Next I
Open "HellGolf.sol" For Input As #2
Do While Not EOF(2)
Line Input #2, TextLine
If Left(TextLine, 8) = "solution" Then GoTo L2
If Left(TextLine, 1) = "s" Then
Length = InStr(TextLine, " ") - 1
'
L1 = InStr(TextLine, "_")
Ar = Mid(TextLine, 2, 1)
Ball = Val(Mid(TextLine, 3, L1 - 3))
Stroke = Val(Mid(TextLine, L1 + 1, Length - L1))
If Stroke = 0 Then
X0 = BallJ(Ball)
Y0 = BallI(Ball)
End If
If Ar = "L" Then
J = X0 - (BallHit(Ball) - Stroke)
I = Y0
ElseIf Ar = "D" Then
J = X0
I = Y0 + (BallHit(Ball) - Stroke)
ElseIf Ar = "R" Then
J = X0 + (BallHit(Ball) - Stroke)
I = Y0
ElseIf Ar = "U" Then
J = X0
I = Y0 - (BallHit(Ball) - Stroke)
End If
ActiveSheet.Shapes.AddLine(ScX / 2 + (X0 - 1) * ScX, ScY / 2 + (Y0 - 1) * ScY, _
ScX / 2 + (J - 1) * ScX, ScY / 2 + (I - 1) * ScY).Select
Selection.ShapeRange.Line.EndArrowheadStyle = msoArrowheadTriangle
Selection.ShapeRange.Line.EndArrowheadLength = msoArrowheadLengthMedium
Selection.ShapeRange.Line.EndArrowheadWidth = msoArrowheadWidthMedium
X0 = J
Y0 = I
End If
L2:
Loop
Close #2
'
'
End Sub

Download Report