昨日作成した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手で解決★
まあ、あまりスッキリしないコードだが自力で解けたので良しとしよう。