バックトラッキングの可視化

バックトラッキングは、再帰に復元の規則を加えます。選択して共有状態を変え、下を探索し、戻るときに必要な変更を取り消します。再帰が探索木を作り、復元が兄弟枝の開始状態をそろえます。

N クイーンは攻撃の制約キーを予約します。順列は要素を確定済みの前半へ交換し、後で戻します。数独は数字を仮置きし、行・列・ブロックの制約を調べ、子の探索が失敗したら空欄へ戻します。

レッスンの比較

N クイーンと数独は制約探索です。部分割り当てが規則を破る、または候補がなくなると、部分木を飛ばせます。順列は全葉を訪れ、復元を中心に扱います。逆交換を省くと、次の枝が誤った配列から始まります。

推奨する学習順序

N クイーンから始めます。一個が三つのキーを持ち、配置で予約し、巻き戻しで解放します。n = 4 のトレースでは、最初の解の前に必ず失敗枝を通ります。

次は順列です。配列そのものが呼び出しの状態で、同じ交換が前進と復元を担います。各ループ前の呼び出し元のスナップショットに注目します。入れ子の逆交換が、深さにかかわらず元の状態を戻します。

最後は数独ソルバーです。MRV が候補の最も少ない空欄を選び、制約行列がその領域を説明します。既定例では候補ゼロのセルが三つの仮置きを再帰から取り消し、正しい根の選択へ戻します。

注目する点

• 最小の可逆な変更を特定します。クイーン一個と三キー、交換一回、セル一つです。
• 拒否と復元を分けます。拒否した候補は状態に入りません。復元する候補は局所的には有効で、深部で失敗したか、その枝の列挙を終えたものです。
• 次の兄弟の選択前に、呼び出し元の状態が戻っているかを確認します。
• 停止規則を調べます。N クイーンと数独は最初の解を返し、順列は葉を記録して続けます。
• 探索順と有効性を分けます。MRV や左からの列選択は軌跡と費用を変えても、有効な完全割り当ては変えません。

バックトラッキングの可視化一覧

失敗枝へ入り、ハイライトされたコードと画面の状態復元を一段階ずつ追ってください。