Le 15-puzzle sert de banc d’essai aux algorithmes de recherche IA depuis les années 60. Chaque génération d’algorithme a été inventée pour franchir le mur où butait la précédente. Cet article les parcourt dans l’ordre d’invention, en expliquant à quoi servait chacun et ce qui rendait le suivant nécessaire.
Années 60 — Recherche en largeur (BFS)
Le premier algorithme correct qu’on essaie. Explorer les états niveau par niveau jusqu’au but.
Pour le 8-puzzle, BFS termine en fractions de seconde. Pour le 15-puzzle, profondeur 80 pour le pire — 4⁸⁰ états, plus que d’atomes dans l’univers observable. BFS ne termine pas.
Le mur : explosion exponentielle. Une recherche non informée est sans espoir au-delà du 3×3.
1968 — A*
Hart, Nilsson et Raphael publient A Formal Basis for the Heuristic Determination of Minimum Cost Paths. Idée : explorer non pas par distance au départ, mais par f = g + h, où h est une estimation d’une borne inférieure sur la distance restante.
Pour le 15-puzzle, h est la distance de Manhattan. Manhattan est admissible et consistante. Avec ces propriétés, A* trouve la solution optimale.
Performance : résout, mais sur les pires instances explore des millions d’états et consomme des centaines de Mo. Mur : mémoire.
1985 — IDA*
Article de Korf. DFS itératif où le seuil est le f-coût, pas la profondeur. Explore les mêmes états qu’A*, sans les retenir entre itérations.
Performance : résout n’importe quel 15-puzzle en secondes sur du matériel 1985, tient en Ko. Mur : l’heuristique reste Manhattan. Pour accélérer il faut plus serré.
Années 90 — Conflit linéaire
Hansson, Mayer, Yung. Manhattan suppose la traversée libre des tuiles. Faux.
Conflit linéaire ajoute 2 coups pour chaque paire de tuiles d’une même rangée appartenant à cette rangée mais en mauvais ordre. Idem colonnes.
Effet : 5–15 % de nœuds en moins sur les durs. Amélioration stricte.
1996 — Walking distance
Précalcule, pour chaque disposition projetée sur les rangées seules, le nombre minimum d’opérations « échange de rangée ». Idem colonnes. Somme.
Admissible et plus serrée — 1,5 à 2× la valeur Manhattan, IDA* explore bien moins de nœuds. Coût : ~500 Ko précalculés pour 4×4.
2002 — Bases additives disjointes
Korf et Felner. La plus forte heuristique connue. Partition disjointe des tuiles (7+8 pour 15-puzzle), précalcul du coût optimal par groupe, somme à la recherche. Admissible.
~1 Go pour le 15-puzzle. Résout le 15-puzzle le pire en millisecondes.
2005+ — bases plus grandes
Même technique au 24-puzzle (partition 5+5+5+9 ~4 Go). Le 35-puzzle est à la frontière ; les pires instances restent ouvertes en 2026.
2010+ — heuristiques par réseau de neurones
Estiment la valeur Manhattan-like, parfois plus serrées. Mais non admissibles en général — plus de garantie d’optimalité. Pour le logiciel qui veut l’optimalité, les bases classiques restent l’outil.
Pourquoi cette histoire compte
Chaque vague de recherche venait du même étau : assez petit pour benchmarker, assez grand pour faire planter le mauvais. Le 15-puzzle a servi de banc d’essai à des avancées générales — A*, IDA*, bases de motifs — qui irriguent maintenant la planification de routes, la démonstration de théorèmes, et bien d’autres domaines.
Quand vous résolvez un 15-puzzle dans une app via un bouton d’indice, vous utilisez des algos développés exactement pour ce jeu puis généralisés.
Tableau récap
| Année | Algorithme | Temps sur 15-puzzle dur | Mémoire | Apport |
|---|---|---|---|---|
| 60 | BFS | Ne termine pas | Énorme | — |
| 1968 | A* + Manhattan | Minutes | Centaines de Mo | Recherche heuristique |
| 1985 | IDA* + Manhattan | Secondes | Ko | Profondeur itérative |
| 1996 | IDA* + walking distance | < 1 s | + 500 Ko précalc | Heuristique meilleure |
| 2002 | IDA* + 7+8 | Millisecondes | + 1 Go précalc | Énumération par sous-ensembles |
Chaque ligne est un vrai saut qualitatif. L’histoire de la résolution du 15-puzzle est aussi celle de la recherche heuristique moderne.