Решая 8-головоломку с помощью BFS

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.