Affrontare l'8-puzzle tramite BFS

Question

Ho sentito dire che il problema 8-puzzle può essere affrontato tramite BFS, ma io non capisco come. Voglio conoscere i passi intermedi che ho bisogno di ottenere da un bordo in questo modo:

3 1 2
6 4 5
0 7 8

a

1 2 3
4 5 6
7 8 0 

Sono i passaggi intermedi "livelli" a una ricerca BFS?

A proposito, questo è compito semplice, non mi importa di ottimalità.

Answer 1

questo è praticamente un modello per qualsiasi ricerca 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)

Nota non stiamo facendo nulla di fantasia come il controllo, motocicli o qualsiasi cosa. se fossimo, coda di modifica a uno stack, e si ottiene DFS.