java - 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が得られます。