Comment utiliser le solveur de taquin
Tapez le numéro de chaque carreau à sa place sur votre plateau, ligne par ligne, et laissez le trou vide. Appuyez ensuite sur Résoudre. Le solveur vérifie le plateau, cherche la solution la plus courte et l'affiche sous forme de liste de carreaux à faire glisser. Appuyez sur Lecture pour la regarder ou avancez avec les flèches. Passez à Faire glisser pour jouer vous-même en touchant les carreaux voisins du trou. Mélanger vous donne un plateau aléatoire résoluble.
Pour la petite version 3 x 3, choisissez Taquin 8. Vous pouvez aussi coller un plateau en texte, par exemple 5 1 2 4 9 6 3 8 13 10 7 11 0 14 15 12, avec 0 ou _ pour le trou.
Tous les taquins sont-ils résolubles ?
Non : exactement la moitié des dispositions ne peuvent pas être résolues, et le solveur vous le dit avant de chercher. Le test repose sur les inversions : lisez les carreaux ligne par ligne et comptez les paires où un grand nombre précède un plus petit.
- Taquin 8 (3 x 3) : résoluble exactement quand le nombre d'inversions est pair. Un glissement le long d'une ligne ne change rien ; un glissement vers le haut ou le bas fait sauter un carreau par-dessus deux autres, ce qui change le compte de 0 ou de 2.
- Taquin 15 (4 x 4) : un glissement vertical fait sauter un carreau par-dessus trois autres, donc le nombre d'inversions change d'un nombre impair pendant que le trou change de ligne. La somme des inversions et de la ligne du trou comptée depuis le bas garde donc toujours sa parité, et sur le plateau résolu elle est impaire. Un plateau où elle est paire ne pourra jamais être résolu.
L'exemple célèbre est un plateau résolu avec le 14 et le 15 échangés : une inversion, trou sur la ligne du bas, total 2, pair, donc impossible.
Comment le solveur trouve la solution la plus courte
Le solveur utilise IDA* (A* à approfondissement itératif), une recherche qui essaie toutes les solutions jusqu'à une longueur limite et relève la limite jusqu'à ce que l'une d'elles fonctionne. Elle est guidée par une estimation du nombre de coups restants qui ne surestime jamais, et c'est ce qui garantit que la première solution trouvée est l'une des plus courtes.
- Pour le taquin de 8, l'estimation est la distance de Manhattan (l'écart de chaque carreau à sa place, en lignes plus colonnes) plus une correction pour les carreaux qui se bloquent dans leur propre ligne ou colonne (conflits linéaires). Chaque taquin de 8 est résolu de façon optimale en une fraction de seconde.
- Pour le taquin de 15, les plateaux faciles sont résolus de la même façon ; pour les plus durs, le solveur construit trois bases de motifs : le nombre exact de coups pour chaque placement des carreaux 1, 5, 6, 9, 10, 13, des carreaux 7, 8, 11, 12, 14, 15 et des carreaux 2, 3, 4. Additionnées, et vérifiées aussi sur le plateau retourné selon sa diagonale, elles donnent une estimation bien plus précise. Leur construction prend une seconde ou deux, dans votre navigateur.
La plupart des taquins de 15 aléatoires sont résolus de façon optimale en quelques secondes. Les positions les plus difficiles demandent jusqu'à 80 coups et peuvent prendre beaucoup plus de temps : la recherche dispose donc d'un budget de 15 secondes. S'il est épuisé, le solveur passe à une méthode rapide (première ligne, puis première colonne, puis le 3 x 3 restant résolu de façon optimale) et indique que cette solution n'est pas la plus courte.
Lors des tests, les résultats du taquin de 8 correspondaient à une table complète des distances exactes des 181 440 positions résolubles, ceux du taquin de 15 à une seconde recherche indépendante, et chaque solution a été rejouée carreau par carreau.
Exemple
Le plateau d'exemple 5 1 2 4 / 9 6 3 8 / 13 10 7 11 / _ 14 15 12 se résout en 9 coups : faites glisser 13, 9, 5, 1, 2, 3, 7, 11, 12. Pour le taquin de 8, essayez 8 6 7 / 2 5 4 / 3 _ 1 : c'est l'une des deux seules positions du taquin de 8 qui demandent 31 coups, le maximum pour ce format.
Astuce pour le résoudre à la main
Résolvez d'abord la ligne du haut, puis la colonne de gauche, et n'y touchez plus : il reste un taquin plus petit. Placez les deux derniers carreaux d'une ligne ensemble en garant le dernier sous sa place, puis en les faisant tourner tous les deux.
Autres casse-têtes où compter ses coups : le compte est bon, où six plaques doivent donner un nombre, le solitaire, où il faut finir avec une seule bille, et 2048, qui fait aussi glisser des tuiles sur une grille de 4 x 4.
Solveur testé le . Une erreur ? Dites-le-nous.
Questions fréquentes
Pourquoi mon taquin est-il impossible ?
La moitié des dispositions ne peuvent pas être atteintes en faisant glisser les carreaux. Si la somme des inversions et de la ligne du trou comptée depuis le bas est paire, aucune suite de glissements ne résout le plateau. Sur un vrai taquin, cela arrive quand deux carreaux ont été sortis et échangés. Échangez deux carreaux quelconques et il devient résoluble.
Combien de coups un taquin de 15 peut-il demander au maximum ?
80 déplacements d'un seul carreau. Des recherches par ordinateur ont montré que toute position résoluble du taquin de 15 se résout en 80 coups ou moins, et que certaines positions en demandent bien 80. Pour le taquin de 8, le maximum est de 31.
La solution est-elle vraiment la plus courte ?
Quand le résultat indique une optimalité prouvée, oui : la recherche a vérifié qu'aucune solution plus courte n'existe. Si le budget de 15 secondes est épuisé sur un plateau très difficile, vous obtenez à la place une solution rapide, clairement signalée comme n'étant pas la plus courte.
Comment compter les inversions ?
Lisez les carreaux ligne par ligne en ignorant le trou. Pour chaque carreau, comptez les carreaux suivants qui portent un plus petit nombre. Additionnez tous ces comptes.
Le solveur envoie-t-il mon plateau quelque part ?
Non. La recherche tourne dans votre navigateur, dans un fil d'exécution en arrière-plan ; rien n'est envoyé.