Comment utiliser le solveur
L’outil ci-dessus résout de manière optimale n’importe quel plateau 3×3 ou 4×4 résoluble — la réponse renvoyée est la séquence de coups la plus courte possible, pas juste une qui marche.
- Appuyez sur Modifier et entrez votre plateau : numérotez les tuiles telles qu’elles doivent se lire dans le taquin terminé (en haut à gauche, c’est le 1), et placez-les là où elles se trouvent actuellement. Vous résolvez un taquin à image — d’un jeu, d’une appli photo, d’un jouet en bois ? Numérotez d’abord mentalement l’image finie de haut-gauche en bas-droite.
- Appuyez sur Résoudre. La liste des coups apparaît instantanément pour un 3×3 et en quelques instants pour un 4×4.
- Rejouez les coups sur votre vrai taquin, un par un.
Si le solveur annonce que le plateau est insoluble, ce n’est pas un bug — exactement la moitié des dispositions ne peut jamais être résolue, et aucune séquence de coups légaux n’y changera rien. Vous préférez apprendre la technique plutôt que lire des coups ? La méthode humaine est ici.
Comment fonctionne un solveur de taquin — six algorithmes comparés
Si vous implémentez un solveur de taquin et hésitez sur l’algorithme, cet article en compare six selon vitesse, mémoire, complexité du code et taille de plateau confortable. Les réponses pour 3×3, 4×4 et 5×5 ne sont pas les mêmes.
1. BFS
L’algorithme correct le plus bête. Explorer les états niveau par niveau jusqu’au but.
- Temps — exponentiel en profondeur. Pour le 8-puzzle, termine en fractions de seconde. Pour le 15-puzzle, ne termine pas avant que la RAM s’épuise.
- Mémoire — garde tout le visité en mémoire. Dizaines de millions d’états pour les 15-puzzles durs.
- Code — vingt lignes.
- Verdict — ok pour 3×3, inutile au-delà.
2. A* avec Manhattan
Le premier vrai algorithme. Même structure que BFS mais les états sortent d’une file de priorité triée par f = g + h, où h est l’heuristique de Manhattan.
- Temps — millisecondes pour le 8-puzzle, secondes à minutes pour le 15.
- Mémoire — garde toujours tout en mémoire ; gérable pour 8, douloureux pour 15.
- Code — cinquante lignes, surtout de la plomberie de file.
- Verdict — l’outil pour le 8-puzzle. À la limite pour le 15.
3. A* avec Manhattan + conflit linéaire
Ajouter 2 coups à l’heuristique pour chaque paire de tuiles dans une même rangée, appartenant à cette rangée mais en mauvais ordre (idem pour colonnes). Elles doivent se croiser, et Manhattan ne le voit pas.
- Temps — typiquement 5–15 % plus rapide qu’A* Manhattan simple.
- Mémoire — inchangée.
- Code — soixante lignes.
- Verdict — strictement meilleur. Toujours l’utiliser.
4. IDA* avec Manhattan + conflit linéaire
A* itératif en profondeur. DFS limité par f-coût, on remonte le seuil à chaque itération. On échange mémoire contre temps en réexplorant.
- Temps — un peu plus lent par nœud à cause des reprises, mais la moindre pression mémoire gagne sur les 15-puzzles durs.
- Mémoire — O(profondeur), pas O(états explorés). C’est le gain.
- Code — quatre-vingts lignes (DFS récursive, gestion de seuil).
- Verdict — l’outil pour le 4×4. Standard depuis Korf 1985.
5. IDA* avec walking distance
Walking distance est plus serrée. Précalculer, pour chaque disposition projetée uniquement sur les rangées (en ignorant la position dans la rangée), le nombre minimum d’opérations « échange de rangée » pour amener chaque tuile dans la bonne rangée. Idem pour colonnes. Somme.
Elle capture ce que Manhattan rate : des tuiles d’une même rangée qui se disputent la même place.
- Temps — typiquement 2× plus rapide que Manhattan + conflit linéaire sur 15-puzzles durs : heuristique plus serrée, IDA* élague plus.
- Mémoire — petite table précalculée (~500 Ko pour 4×4).
- Code — 150 lignes. La précompute est un BFS sur un espace réduit.
- Verdict — l’outil pour le 4×4 si vous avez le budget ingénierie. Première amélioration non triviale.
6. IDA* avec bases additives disjointes
L’heuristique la plus forte connue. Partitionner les tuiles en groupes disjoints (la partition 7+8 pour 15-puzzle est standard). Pour chaque groupe, précalculer le coût optimal pour amener ses tuiles à leurs positions cibles, en ignorant les autres. Tabuler toutes les dispositions possibles du groupe.
À la recherche, lire la contribution de chaque groupe et sommer. Grâce à la disjonction et à un argument soigné, la somme est admissible.
- Temps — résout le 15-puzzle le plus dur en millisecondes. Résout un 24-puzzle aléatoire en secondes.
- Mémoire — substantielle. Une 7+8 pour 15-puzzle ~1 Go. Une 5+5+5+9 pour 24-puzzle ~4 Go. La mémoire domine l’ingénierie.
- Code — 300+ lignes. La précompute par BFS rétrograde fait la majeure partie du travail.
- Verdict — l’outil pour 5×5 et 6×6. Surdimensionné pour 3×3.
Recommandations résumées
Pour écrire un solveur aujourd’hui :
- 3×3 : A* + Manhattan + conflit linéaire. Plus, c’est du sur-engineering.
- 4×4 : IDA* + walking distance. Les bases de motifs apportent un gain marginal à cette taille ; pas rentable.
- 5×5 : IDA* + bases additives (5+5+5+9 standard). Sans bases, vous timeout sur les pires instances.
- 6×6 (35-puzzle) : mêmes algos pour des instances aléatoires, mais les pires restent des questions ouvertes. La plupart des apps ne tentent pas.
Et le machine learning ?
Question raisonnable en 2026. Les heuristiques par réseau de neurones sont étudiées depuis 2014 et produisent parfois des heuristiques rapides. Hic : elles sont en général non admissibles — peuvent surestimer — donc plus de garantie d’optimalité. Pour qui livre du logiciel et veut l’optimalité (calibration de difficulté), les bases classiques restent le bon outil.
Pour la recherche, des bases entraînées par réseau apportent des accélérations légères sur les pires instances. Utile pour les articles, marginal pour le logiciel.
Ce qui finit dans une vraie app
Une app mobile en prod qui veut un solveur pour les indices atterrit presque toujours sur :
- IDA* + walking distance pour 4×4.
- IDA* + petite base pour 5×5.
- Un seul appel « prochain coup » depuis le bouton d’indice.
- Tout sur l’appareil. Le solveur entier = quelques centaines de Ko de code plus quelques Mo de tables précalculées.
C’est la bonne pile pragmatique pour un jeu mobile calme. Le bouton d’indice de Slide Puzzle fonctionne exactement comme ça.