Deux manières de résoudre un 15-puzzle. La première, celle que tout joueur finit par découvrir : résoudre la rangée du haut, puis la colonne de gauche, et récursion. La seconde, celle des ordinateurs : recherche heuristique sur des millions d’états guidée par une borne inférieure intelligente du nombre de coups restants.
Ce guide couvre les deux, dans l’ordre où on les apprend.
Le 15-puzzle en un paragraphe
Plateau 4×4, quinze tuiles numérotées, une case vide. On glisse les tuiles dans le trou jusqu’à ordonner 1 à 15, vide en bas-droite. Plateau inventé par Noyes Chapman en 1874, devenu une folie internationale dans les années 1880 après que Sam Loyd a offert 1000 $ pour résoudre une variante insoluble. C’est, au fond, le même jeu que le 8-puzzle — juste une rangée et une colonne de plus.
À la main : la méthode rangée-et-colonne
La technique que tout le monde finit par trouver :
- Résoudre la rangée 1. Placer 1 et 2. Puis 3 dans le coin haut-droit. La manœuvre en L — amener 4 à la position 3, glisser 3 dessous, tourner la paire en place — est le truc qui rend les angles possibles.
- Résoudre la colonne 1. Placer 5, puis 9, puis 13 dans l’angle bas-gauche avec la même astuce d’angle.
- Récursion. Reste un sous-puzzle 3×3 (avec la colonne droite et la rangée du bas), c’est un 8-puzzle que vous savez déjà résoudre.
Un joueur sûr fait un 15-puzzle à la main en 3 à 5 minutes. Un débutant peut mettre 20 minutes au premier essai et un tiers au troisième.
La même méthode passe à l’échelle en 5×5 et 6×6. La récursion termine toujours sur une fin de partie 3×3.
Solveur optimal : A* avec distance de Manhattan
Un ordinateur peut faire bien mieux. Concrètement : trouver la solution la plus courte, ce que les humains ne jouent presque jamais.
Fait mathématique : le 15-puzzle médian demande environ 52 coups en optimal. Le pire fait 80. La méthode rangée-et-colonne en fait typiquement 100–150 sur le même plateau.
Pour trouver l’optimum, A* traite chaque état comme un nœud, chaque coup comme une arête, et demande : combien de coups jusqu’au but, au minimum ? Le minimum exact est impossible à calculer sans résoudre, mais une bonne borne inférieure rend A* rapide.
La borne classique est la distance de Manhattan :
Pour chaque tuile, somme de l’écart de rangées et de colonnes entre sa position courante et sa position cible. (On ignore la case vide.)
Manhattan est admissible — elle ne surestime jamais la distance réelle, puisque chaque tuile doit parcourir au moins ce trajet. Avec A* et Manhattan, le 8-puzzle se résout en microsecondes et le 15-puzzle en secondes.
IDA* : le cousin économe en mémoire
A* doit mémoriser chaque état exploré. Pour les 15-puzzles, ce sont des centaines de Mo de RAM sur les plus durs. Iterative-deepening A (IDA)** échange mémoire contre temps en faisant un DFS limité par f-coût avec l’heuristique, en relevant la limite à chaque itération.
IDA* est ce qu’utilise tout solveur de référence pour le 15-puzzle. L’article de Korf de 1985 a introduit IDA* précisément pour résoudre les 15-puzzles à l’optimum sur le matériel du début des années 80.
Au-delà de Manhattan : walking distance et bases de motifs
Manhattan est rapide mais lâche. Elle suppose que les tuiles peuvent se traverser. Elles ne peuvent pas — deux tuiles d’une même rangée doivent se croiser, ce qui coûte des coups en plus.
Walking distance compte ces coups en plus. On précalcule, pour chaque paire de rangées, le nombre minimum d’opérations « échange de rangée » pour permuter les tuiles dans les bonnes rangées. Même chose pour les colonnes. On somme. Le résultat est démontrablement plus serré que Manhattan — typiquement 25 % de plus, ce qui veut dire qu’A*/IDA* explore 25 % moins de nœuds.
L’heuristique la plus forte connue est la base de motifs additive disjointe :
- Partitionner les tuiles en groupes disjoints (la partition 5-5-5 plus le vide est courante).
- Pour chaque groupe, précalculer pour chaque disposition possible des tuiles du groupe le nombre minimum de coups pour les amener à leurs cibles, en ignorant les autres.
- À la recherche, additionner les lookups par groupe.
Une partition 7+8 pour le 15-puzzle pèse environ 1 Go en stockage mais permet à IDA* de résoudre n’importe quel 15-puzzle en millisecondes. Pour le 24-puzzle (5×5), les bases de motifs sont essentiellement la seule voie pratique.
Pourquoi la résolution manuelle est souvent plus rapide (pour une partie)
Petite remise en perspective : écrire A*, choisir une heuristique et attendre qu’il termine, c’est plus long que prendre un 15-puzzle et le résoudre à la main. La math est intéressante ; en pratique, qui connaît la méthode rangée-et-colonne résout n’importe quel plateau en cinq minutes.
Les solveurs comptent pour l’agrégat : articles comparant des heuristiques sur des milliers d’instances aléatoires, manuels d’IA utilisant le 15-puzzle comme banc d’essai, et apps qui doivent générer des puzzles garantis résolubles en environ N coups pour calibrer la difficulté.
Ordre de lecture suggéré
Si vous êtes ici pour écrire un solveur : commencez par A*/Manhattan, regardez-le résoudre quelques 8-puzzles, puis portez-le en IDA* pour le 15-puzzle. Walking distance est ensuite un ajout de 100 lignes qui double la vitesse. Les bases de motifs sont un projet de week-end qui apporte encore un ordre de grandeur.
Si vous êtes ici pour jouer : apprenez d’abord la méthode rangée-et-colonne, lisez ensuite pourquoi certains plateaux sont insolubles, puis revenez ici pour la théorie.