VBA 再帰の応用 ～ バックトラックアルゴリズムで油分け算パズルを解く

昨日作成したCupクラスを使って、バックトラック法で油分け算を解いてみた。
thom.hateblo.jp

バックトラック法というのは、例えば迷路などで分かれ道に差し掛かったとき、とりあえず片方に進んで行き止まりだったら一つ前の分岐点まで引き返すという方法。
要するにしらみつぶしに調べるという力技である。バックトラック法のアルゴリズムは通常、再帰で実装する。

もともと書籍に書いてある方法もバックトラック法である。
書籍のやりかたは、全ての状態を洗い出し、ある状態からある状態へ遷移可能かどうかをチェックしながら進めていくというもの。
私が書いた方は実際に注ぎながらのバックトラックである。

Dim L3 As Cup, L5 As Cup, L8 As Cup
Dim 履歴 As Collection
Dim 正解コレクション As Collection
#Const 経過表示 = False

Sub 自動油分け算()
    Set L3 = New Cup: L3.最大容量 = 3
    Set L5 = New Cup: L5.最大容量 = 5
    Set L8 = New Cup: L8.最大容量 = 8
    L8.内容量 = 8
    Set 履歴 = New Collection
    履歴.Add CStr(L3.内容量) & CStr(L5.内容量) & CStr(L8.内容量)
    
    Set 正解コレクション = New Collection
    バックトラック L8, L5, "L8->L5", 1
    バックトラック L8, L3, "L8->L3", 1
    
    Debug.Print 正解コレクション.Count & " パターン見つかりました。"
    For Each x In 正解コレクション
        Debug.Print x
    Next
End Sub

Sub バックトラック(注ぎ元 As Cup, 注ぎ先 As Cup, Log As String, cnt As Long)
    '注ぐ前に値を保管
    L3容量 = L3.内容量
    L5容量 = L5.内容量
    L8容量 = L8.内容量
    
    注ぎ元.注ぐ 注ぎ先
    
    If "044" = CStr(L3.内容量) & CStr(L5.内容量) & CStr(L8.内容量) Then
        終了理由 = "★" & cnt & "手で解決★"
        正解コレクション.Add Log & ", " & 終了理由
        GoTo Quit
    Else
        For Each h In 履歴
            If h = CStr(L3.内容量) & CStr(L5.内容量) & CStr(L8.内容量) Then
                終了理由 = "千日手です。"
                GoTo Quit
            End If
        Next
    End If
    履歴.Add CStr(L3.内容量) & CStr(L5.内容量) & CStr(L8.内容量)

    バックトラック L5, L8, Log & ", L5->L8", cnt + 1
    バックトラック L3, L5, Log & ", L3->L5", cnt + 1
    バックトラック L5, L3, Log & ", L5->L3", cnt + 1
    バックトラック L8, L3, Log & ", L8->L3", cnt + 1
    バックトラック L3, L8, Log & ", L3->L8", cnt + 1
    バックトラック L8, L5, Log & ", L8->L5", cnt + 1

    終了理由 = "同階層の探査終了"
    履歴.Remove 履歴.Count
Quit:
    #If 経過表示 Then
        Debug.Print Log & ", " & 終了理由
        Debug.Print "L8 "; L8.内容量, "L5 "; L5.内容量, "L3 "; L3.内容量
    #End If
    
    '内容量を元にもどす。
    L3.内容量 = L3容量
    L5.内容量 = L5容量
    L8.内容量 = L8容量
End Sub

コップの受け渡しをどうしようかと悩んだが、クラスで作ったのが災いして再帰プロシージャにコピー渡しができない。
余計な引数を増やすくらいなら。。ということでモジュールレベル変数とした。
Historyと正解コレクションも同様である。
（もう少しうまいやり方があると思う）

また、解決or千日手ではあえてGoToステートメントを使用した。
GoToレスにこだわる場合はフラグで処理することになるが、それもそれで分かりにくいコードになるので、後始末付きExitとしてのGoToは有りだと思う。

ちなみに、実行結果はこのようになる。

16 パターン見つかりました。
L8->L5, L5->L3, L5->L8, L3->L5, L8->L3, L3->L5, L5->L8, L3->L5, L8->L3, L3->L5, ★10手で解決★
L8->L5, L5->L3, L3->L8, L5->L3, L8->L3, L3->L5, L8->L3, L3->L5, L5->L8, L3->L5, L8->L3, L3->L5, ★12手で解決★
L8->L5, L5->L3, L3->L8, L5->L3, L8->L5, L5->L3, L5->L8, L3->L5, L8->L3, L3->L5, L5->L8, L3->L5, L8->L3, L3->L5, ★14手で解決★
L8->L5, L5->L3, L3->L8, L5->L3, L8->L5, L5->L3, L3->L8, ★7手で解決★
L8->L5, L5->L3, L3->L8, L5->L3, L8->L5, L5->L3, L8->L5, L5->L8, L3->L5, L8->L3, L3->L5, L5->L8, L3->L5, L8->L3, L3->L5, ★15手で解決★
L8->L5, L5->L3, L3->L8, L5->L3, L8->L5, L8->L3, L5->L8, L3->L5, L8->L3, L3->L5, L5->L8, L3->L5, L8->L3, L3->L5, ★14手で解決★
L8->L5, L5->L3, L8->L5, L5->L8, L3->L5, L8->L3, L3->L5, L5->L8, L3->L5, L8->L3, L3->L5, ★11手で解決★
L8->L5, L8->L3, L5->L8, L3->L5, L8->L3, L3->L5, L5->L8, L3->L5, L8->L3, L3->L5, ★10手で解決★
L8->L3, L3->L5, L8->L3, L3->L5, L5->L8, L3->L5, L8->L3, L3->L5, ★8手で解決★
L8->L3, L3->L5, L8->L3, L3->L5, L5->L8, L3->L5, L8->L3, L8->L5, L3->L8, L5->L3, L3->L8, L5->L3, L8->L5, L5->L3, L3->L8, ★15手で解決★
L8->L3, L3->L5, L8->L3, L3->L5, L5->L8, L3->L5, L8->L5, L5->L3, L3->L8, L5->L3, L8->L5, L5->L3, L3->L8, ★13手で解決★
L8->L3, L3->L5, L8->L3, L3->L5, L8->L3, L3->L8, L5->L3, L3->L8, L5->L3, L8->L5, L5->L3, L3->L8, ★12手で解決★
L8->L3, L3->L5, L8->L3, L3->L5, L3->L8, L5->L3, L3->L8, L5->L3, L8->L5, L5->L3, L3->L8, ★11手で解決★
L8->L3, L3->L5, L8->L3, L8->L5, L3->L8, L5->L3, L3->L8, L5->L3, L8->L5, L5->L3, L3->L8, ★11手で解決★
L8->L3, L3->L5, L8->L5, L5->L3, L3->L8, L5->L3, L8->L5, L5->L3, L3->L8, ★9手で解決★
L8->L3, L8->L5, L3->L8, L5->L3, L3->L8, L5->L3, L8->L5, L5->L3, L3->L8, ★9手で解決★

まあ、あまりスッキリしないコードだが自力で解けたので良しとしよう。