Un solveur de taquin est un programme qui, depuis n’importe quelle position de départ résoluble, sort une suite de coups menant au but. C’est un outil pour deux publics : les joueurs coincés, et les développeurs qui livrent une app.
Les deux publics veulent des choses très différentes.
Pourquoi les joueurs n’en ont presque jamais besoin
Si vous êtes coincé, la vraie solution n’est généralement pas « lancer un solveur ». C’est l’un des trois :
- Apprendre la méthode rangée-et-colonne. La plupart des abandons sont des joueurs qui n’ont jamais appris la stratégie canonique. (Commencez par le 8-puzzle, puis montez.)
- Vérifier que le puzzle est résoluble. Si rien ne marche, l’app a peut-être généré un plateau insoluble. Vérifiable rapidement.
- Demander un indice, pas la solution. Le prochain coup unique suffit en général. Les apps qui offrent des indices (la nôtre, en Premium) calculent un coup à la demande, pas une solution complète.
Une solution complète n’apprend presque rien d’utile, parce que le solveur sort une suite optimale — typiquement 52 coups pour un 15-puzzle dur — et regarder 52 coups défiler ne bâtit pas d’intuition.
L’indice est la bonne unité. Qui a besoin d’un indice n’a pas besoin d’un solveur.
Pourquoi les développeurs en ont besoin, eux
Construire une app de taquin, c’est s’engager sur plusieurs promesses :
- Tout puzzle est résoluble.
- Tout puzzle réclame à peu près un nombre donné de coups (calibration de difficulté).
- Tout puzzle peut donner un indice à la demande.
Aucune n’est honnête sans solveur tournant en arrière-plan.
Génération « résoluble par construction » : remonter depuis le but en appliquant des coups valides aléatoires garantit une position initiale résoluble. La plupart des apps font ça, la nôtre comprise.
Calibration de difficulté : on veut un puzzle « intéressant » — ni trivial (presque résolu) ni épuisant (60 coups en 3×3). Astuce classique : appliquer assez de coups arrière pour atterrir près de la distance optimale — typiquement 20–30 en 3×3, 40–60 en 4×4. Le solveur vérifie la distance après génération.
Indices : il faut un solveur capable de produire un bon prochain coup en quelques centaines de millisecondes. Plus rapide qu’une solution complète, mais ça exige du vrai travail algorithmique.
Quel solveur
Selon la taille :
| Plateau | Algorithme conseillé | Temps par résolution |
|---|---|---|
| 3×3 | A* + Manhattan | < 1 ms |
| 4×4 | IDA* + walking distance | 10 ms – 1 s |
| 5×5 | IDA* + base 5+5+5+9 | 100 ms – minutes |
| 6×6 | IDA* + base plus grande | secondes – heures |
Pour 3×3, même BFS brute marche. À 4×4 il faut une vraie heuristique, et Manhattan est la norme depuis les années 80. À 5×5, il faut des bases de motifs. À 6×6, c’est de la recherche.
Détails des algorithmes dans le guide du solveur du 15-puzzle et le solveur du 8-puzzle. Comparatif sur la page solveur — comparatif.
Sur l’appareil vs côté serveur
Deux options pour les apps mobiles avec solveur : sur l’appareil ou via serveur.
Sur l’appareil est le choix le plus honnête pour une app respectueuse de la vie privée. Le solveur fait quelques centaines de lignes, les bases pour 4×4 tiennent en quelques Mo, et un téléphone moderne résout n’importe quel 15-puzzle largement en moins d’une seconde. Pas de raison d’envoyer un état à un serveur — et ne pas l’envoyer, c’est l’une des choses qui distinguent un jeu calme d’un qui a besoin de télémétrie pour fonctionner.
Côté serveur s’utilise quand le développeur veut suivre les puzzles sur lesquels les gens coincent, ou faire de l’A/B test de courbes de difficulté. Vraies raisons produit, mais qui coûtent en vie privée et en dépendance réseau. Une app qui ne résout pas hors-ligne ne marche pas en avion.
Slide Puzzle résout entièrement sur l’appareil. La base 4×4 fait ~6 Mo et vit dans le bundle. Le bouton d’indice s’en sert directement. Aucune requête ne part du téléphone.
Note pragmatique
Si vous êtes ici à chercher « un site solveur où je colle mon plateau et il me dit la réponse » — ça existe, et ce sont souvent des solveurs web pour 8-puzzle. Pour le 3×3, ça va. Pour 4×4 et plus, l’expérience est inconfortable : taper 16 nombres, regarder 50 coups, essayer de reproduire 50 coups sur un plateau physique. Personne n’aime ça.
Les usages réalistes :
- Vérifier votre propre implémentation.
- Générer un corpus de tests.
- Calculer un indice dans une app.
À part ça, apprendre la méthode rangée-et-colonne est plus rapide.