左手法


左手法とは,左側の壁に沿って迷路を探索する手法である.迷路が木構造になっている場合のみ,ゴールへの到達が保証されている.スタックなどを使わずとも,自然にバックトラッキング(深さ優先探索)の探索が実現される点が特徴.左手法のソースコードを以下に示す.

拡張左手法とは,探索途中に仮想的な壁を立てることで,任意の2次元格子状迷路に対してゴールの到達を保証する手法である.

厳密なルールの記述は難しいので,以下に拡張左手法の実装例を紹介する.(意外とコーディングは厄介です.)