 Décrivez un algorithme pour résoudre le jeu "8-puzzle".
Le 8-puzzle est un puzzle coulissant qui demande au joueur de faire glisser des tuiles numérotées dans une grille 3x3 pour compléter le puzzle. L'algorithme pour résoudre ce casse-tête comprend une technique de recherche en largeur d'abord. Cela implique de créer une liste de nœuds contenant l'état actuel du puzzle (position et ordre des cases) ainsi que les états précédents (pour minimiser la recherche d'états en double). L'algorithme procède ensuite au déplacement de chaque tuile vers l'espace vide et évalue si le nouvel état résultant est un nœud d'objectif (c'est-à-dire la fin du puzzle). Si ce n'est pas le cas, le programme passe au nœud suivant, gardant une trace des nœuds déjà visités et enregistrant en continu les nouveaux états pour une évaluation plus approfondie. Une fois le nœud cible identifié, le programme calcule le chemin optimal du nœud de départ au nœud cible.