Tackling the 8-puzzle via BFS

Question

J'ai entendu dire que le problème des 8 puzzles pouvait être résolu via BFS, mais je ne comprends pas comment. Je veux connaître les étapes intermédiaires que je dois obtenir d'un conseil d'administration comme celui-ci:

3 1 2 
6 4 5 
0 7 8 

à

1 2 3 
4 5 6 
7 8 0 

sont les étapes intermédiaires « niveaux » sur une recherche BFS? Au fait, ceci est un devoir de base, je ne me soucie pas de l'optimalité.

Answer 1

c'est à peu près un modèle pour toute recherche 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) 

note que nous ne faisons rien de fantaisie comme la vérification des cycles ou quoi que ce soit. si nous étions, changez la file d'attente à une pile, et vous obtenez DFS.