レイトン教授とグラフ探索アルゴリズム

「レイトン教授と最後の時間旅行 - 猫とC#について書くmatarilloの雑記」で書いたグラフを探索するプログラムを書いてみた。
最初は深さ優先探索(DFS)で試してみたのだが、なかなか解が見つからない。
どうやら、明らかに無駄な(解がない)ところを一生懸命探索している。
解空間は4^30 = 2^60 = 1.15e18か。変なところにはまり込むと嫌だな。枝刈りが必要だ。
ということでアドホックに枝刈りルールを追加していったら解けるようになった。
でもこれはちょっと馬鹿らしいな。枝刈りをマシにするか、幅優先探索(BFS)にするか、どっちがいいのかな。