このプログラムの動きの正体

このプログラムは、一言でいうと「超・慎重派で記憶力が完璧な人が、あらゆる可能性を順番に試していく作戦（幅優先探索）」で動いています。

人間がこのパズルを解くときの頭の中をイメージしながら、プログラムの3つのステップを説明してみましょう。

① 最初の手（1手目）をすべて書き出す

まず、スタートの盤面から「1手で動かせるパターン」をすべて実際に動かしてみます。

空白マスの隣にある駒を動かすと、今回の場合は「下」「左」「上」の3つの盤面（選択肢）が生まれます（図2の①、②、③の盤面） 。

プログラムは、この生まれた3つの選択肢を、「次に調べる候補リスト（キュー）」のノートにメモします 。

② 2手目の選択肢を、横並びで順番に平等に調べる

ここがこのアルゴリズム（幅優先探索）の最大の特徴です。どれか1つのルートをいきなり深く掘り下げることはしません。

ノートにメモした「1手目の選択肢」を順番に取り出します 。

1番目の選択肢から「さらに1手（合計2手）動かした形」を書き出します 。

それが終わったら、次は2番目の選択肢から「さらに1手動かした形」を書き出します 。

このように、「すべてのルートを平等に、まずは1手、次はすべて2手、次はすべて3手……」と、水面が広がるように横に並行して調べていきます 。

③ 「これ、さっき見たわ！」という無駄を絶対に省く（超重要）

パズルをガチャガチャ動かしていると、「駒を右に動かして、次の手ですぐ左に戻した」というような、「同じ盤面に戻ってしまう無駄な動き」が必ず発生します 。

人間なら「あ、これさっきやったな」と感覚で気づきますが、プログラムはそれを完璧に覚えるために、「これまでに現れたすべての盤面リスト（check_list）」という専用のアルバムを作っています 。

新しい盤面ができるたびにアルバムをめくり、「あ、アルバムに載ってる（すでに調べた形だ）」と気づいたら、そのルートは「これ以上調べても無駄（終端ノード）」としてその場でバッサリ切り捨てます 。

この徹底した「アルバムチェック」のおかげで、無限ループに陥ることなく、最短ルートだけを絞り込むことができます 。

「手数：31」が意味すること

この並行してしらみつぶしに探すルール（幅優先探索）で進めると、「ゴールが見つかった瞬間の手数が、絶対に一番効率の良い『最短の手数（最小解）』になる」という強力なメリットがあります 。

3手のルートを全部調べ、4手のルートを全部調べ……と進めていって、ようやく31手の全ルートを調べている最中に「あ！ゴールと同じ形（1,2,3...）になった！ 」と見つかったため、このログは「これより短い手数では絶対に解けない、綺麗な31手の最短ルート」を示してくれているのです 。