BFS経由で8パズルに取り組む

Question

8パズルの問題はBFSを介して取り組むことができると聞いたことがありますが、その方法はわかりません。このようなボードから取得する必要がある中間の手順を知りたいです。

3 1 2
6 4 5
0 7 8

に

1 2 3
4 5 6
7 8 0 

BFS検索の中間ステップ「レベル」はありますか？

ちなみに、これは基本的な宿題です。私は最適性を気にしません。

Answer 1

これは、BFS検索のテンプレートです

function next_boards(board)
   yields a set of reachable in one move from the current board

queue = [start_board]

while true:
   current = queue.pop()
   if current = goal: break

   queue.push for all next_boards(current)

サイクルなどをチェックするような派手なことは何もしていないことに注意してください。もしそうなら、キューをスタックに変更すると、DFSが得られます。