Solveur du 8-puzzle — A* avec Manhattan en une page

Le 8-puzzle est le plus petit problème de recherche intéressant. Une implémentation A* de manuel avec distance de Manhattan résout chaque instance en microsecondes. Voici comment, avec le squelette de code que vous pouvez implémenter dans n’importe quel langage.

Mis à jour 2026-05-20 7 min de lecture

Le 8-puzzle, c’est ce qu’on écrit le jour où on découvre la recherche heuristique. Assez petit pour que presque toute approche marche, assez grand pour que les mauvaises soient visiblement inférieures. Cet article suit la solution standard de bout en bout.

L’état

Représenter le plateau comme un tableau de neuf entiers, indexés 0..8 en ordre rangée-majeure :

positions :   indices :
 1 2 3        0 1 2
 4 5 6   ↔   3 4 5
 7 8 _        6 7 8

La case vide est un sentinelle — typiquement 0. État cible : [1, 2, 3, 4, 5, 6, 7, 8, 0].

Les coups

Depuis une position où le vide est à l’indice e, on peut échanger le vide avec ses voisins orthogonaux : e-3 (au-dessus) hors rangée du haut, e+3 (dessous) hors rangée du bas, e-1 (gauche) hors colonne gauche, e+1 (droite) hors colonne droite.

Une fonction neighbors(state) renvoie jusqu’à quatre états atteignables en un coup.

L’heuristique : distance de Manhattan

Pour chaque tuile (en ignorant le vide), somme de l’écart en rangées et en colonnes entre sa position courante et sa cible. Somme sur les tuiles. Cette somme est une borne inférieure du nombre de coups restants — chaque tuile doit parcourir au moins ça.

En pseudo-code :

h(state) = somme sur les tuiles t :
  abs(row(courante) - row(cible)) + abs(col(courante) - col(cible))

Manhattan est admissible (jamais surestimée) et consistante (vérifie l’inégalité triangulaire). Les deux comptent pour A*.

A* en douze lignes

A* maintient une file de priorité d’états triée par f = g + h, où g est la profondeur (coups effectués) et h l’estimation. À chaque itération : sortir l’état de plus petit f, l’expanser, mettre les voisins avec leur f mis à jour.

open = priority_queue()
open.push(start, f=h(start))
came_from = {}; g = {start: 0}

while open is not empty:
  state = open.pop()
  if state == goal: return reconstruct_path(came_from, state)
  for n in neighbors(state):
    tentative_g = g[state] + 1
    if n not in g or tentative_g < g[n]:
      g[n] = tentative_g
      came_from[n] = state
      open.push(n, f=tentative_g + h(n))

C’est tout le solveur. Implémentez h, implémentez neighbors, vous résolvez n’importe quel 8-puzzle.

Performance

A* avec Manhattan résout n’importe quel 8-puzzle en quelques centaines de microsecondes, en développant quelques centaines à quelques milliers d’états sur les instances les plus dures. L’espace d’états est assez petit pour qu’A* domine IDA* à cette taille — A* est le bon choix pour le 3×3, IDA* prend le relais en 4×4 et plus.

Pièges habituels

Trois choses ratées à la première tentative :

Hachage d’état. Les tuples Python se hachent bien ; les tableaux d’ints Java non. Quel que soit le langage, l’état doit être hachable pour que les ensembles open/closed marchent. Astuce courante : encoder l’état 9-tuiles en un entier 32 bits (4 bits par case, vu que les cases vont de 0 à 8).

Oublier la vérification de parité des inversions. Si vous générez un 8-puzzle aléatoire en mélangeant, la moitié sont insolubles, et A* parcourra tout le demi-espace de 181 440 états à chercher un chemin inexistant. Ajoutez un test de parité avant A*, ou générez en remontant depuis le but.

Traiter le vide comme une tuile dans l’heuristique. Manhattan se somme uniquement sur les vraies tuiles. Inclure le vide gonfle l’heuristique et casse l’admissibilité (on peut « corriger » le vide gratuitement).

Au-delà de Manhattan

On peut faire mieux que Manhattan sur le 8-puzzle, mais pas beaucoup :

Conflit linéaire — si deux tuiles d’une rangée appartiennent à cette rangée mais sont en mauvais ordre, il faut au moins 2 coups en plus pour qu’elles se croisent. +2 par conflit. Améliore Manhattan de 5–15 %.
Bases de motifs — précalcul du coût optimal sur des sous-ensembles. Coût mémoire énorme pour un gain minime au 8-puzzle. Utile pour le 15-puzzle, pas ici.

Pour le 8-puzzle, Manhattan + conflit linéaire est le bon compromis pratique.

Ensuite

Si vous avez écrit un solveur 8-puzzle, les suites naturelles :

Solveur du 15-puzzle avec IDA* + walking distance. Mêmes idées, recherche plus profonde. (Guide ici.)
Solveur N-puzzle généraliste avec bases de motifs. Projet de week-end.
Test de solvabilité — fonction de 30 lignes qui dit true si un plateau est atteignable depuis le but. Utile pour le dev d’app. (À partir du théorème de parité.)

Le 8-puzzle est petit. Les techniques apprises ici passent à l’échelle jusqu’en haut.