マッチ棒パズル・最長経路問題の考察１を示します。
（考察１）
与えられたm×nの配置において、プログラム（ML131.bas）を使い、最長の経路を考察せよ。
●プログラム（ML131.bas）
与えられたマッチ棒の配置において、マッチ棒の頭の方向に進むとき、たどれる経路中、最長経路を列挙する。マッチ棒には、番号を付け、経路は番号の並びで表す。
' << ML131.bas >>
' マッチ棒パズル・最長経路問題
' キーボードからマッチ棒配置データを入力。
'
Public C(99,9): ' 与えられたマッチ棒の図形において、マッチ棒の
' 後続関係を保存する配列。
Public X(99): ' 経路を保存する配列。
Public Y(99): ' 番号Tが未通過ならY(T)=0、通過したならY(T)=1。
Public COUNT: ' 経路の個数。
Public KMAX: ' 最長の経路のマット棒の本数。
'
' マッチ棒・配置の入力。
' Eはマッチ棒・本数。マッチ棒に1～Eまでの番号を付ける。
Input"マッチ棒・本数の入力";E
For I=1 To E
S$="マッチ棒番号 "+Str$(I)+" に続くマッチ棒番号を"
S$=S$+Chr$(13)+Chr$(10)+"カンマで区切って入力（ない場合は0）"
T$=InputBox(S$)
'
J=1
While T$ <> ""
R$=Split$(T$,",")
C(I,J)=Val(R$)
J=J+1
Wend
C(I,J)=0
Next I
'
' マッチ棒・配置の表示。
Print"マッチ棒番号 後続番号"
For I=1 To E
Print Using"######## ";I;
J=1
While C(I,J) <> 0
Print Using"####";C(I,J);: J=J+1
Wend
Print
Next I
Print
'
' 最長経路の探索。
COUNT=0
KMAX=0
For T=1 To EMAX: Y(T)=0: Next T
For I=1 To E
X(1)=I: Call Search(1)
Next I
Print"経路の長さの最大値：";KMAX
Print"最長経路の個数:";COUNT
End
'
' 後続番号(C(*,*))を基に最長経路探索を行い、経路を列挙する手続き。
Sub Search(K)
' 経路中( X(1),X(2),…,X(K-1) )に番号X(K)を探す。
If Y(X(K)) > 0 Then
' 経路中に番号X(K)が見つかった場合、経路を表示し戻る。
If K-1 >= KMAX Then
If K-1 > KMAX Then KMAX=K-1: COUNT=0
COUNT=COUNT+1
Print Using"[###] ";COUNT;
Print Using"経路の長さ###: ";K-1;
For I=1 To K-1
Print Using"###";X(I);
Next I
Print
End If
EXit Sub
Else
' 経路中に番号X(K)が見つからなかった場合。
' 番号X(K)に続く番号がない場合、経路を表示し戻る。
If C(X(K),1) = 0 Then
If K >= KMAX Then
If K > KMAX Then KMAX=K: COUNT=0
COUNT=COUNT+1
Print Using"[###] ";COUNT;
Print Using"経路の長さ###:";K;
For I=1 To K
Print Using"###";X(I);
Next I
Print
End If
Exit Sub
End If
' 番号X(K)に続く番号がある場合、経路の探索を続ける。
Y(X(K))=1
J=1
While C(X(K),J) <> 0
X(K+1)=C(X(K),J)
Call Search(K+1)
J=J+1
Wend
' 番号X(K)から先の探索が終わったので戻る。
Y(X(K))=0
Exit Sub
End If
End Sub
