これで新しい盤面を生成することができます。格納する局面を生成してキューに追加します。あとのプログラムは簡単なので説明は割愛します。●実行結果これでプログラムは完成です。それでは実行してみましょう。手で解くことができました。今回は同一局面のチェックに二分探索木を使いましたが、ハッシュ法だともう少し速くなると思います。興味のある方は試してみてください。通りの局面があります。スタートの局面はその一つです。最長手数の局面は、幅優先探索を使って求めることができます。これはあとで試してみましょう。パズルようにゴールの状態が明確な場合、スタートから探索するだけではなくゴールからも探索を行うことで、幅優先探索を高速化することができます。search)」といいます。その理由を説明するために、簡単なシミュレーションをしてみましょう。手で解けると仮定します。手まで探索した時点で同じ局面に到達する、つまり、解を見つけることができます。生成される局面数はぐっと少なくなりますね。局面数が減少すると同一局面の探索処理に有利なだけではなく、「キューからデータを取り出して新しい局面を作る」という根本的な処理のループ回数を減らすことになるので、処理速度は大幅に向上するのです。それではプログラムを作りましょう。つの探索処理を交互に行うことになりますが、そうするとプログラムの大幅な修正が必要になります。ここは、探索方向を示すフラグを用意することで、一つのキューだけで処理することにしましょう。