Au Taquin, ce n’est pas la méthode qui coûte des coups, c’est de jouer une étape à la fois
La méthode classique du Taquin range la grille par morceaux : la première rangée, puis la suivante, puis les deux dernières rangées colonne par colonne, et enfin le petit carré du coin. Chaque zone terminée est « verrouillée », on n’y touche plus. Elle marche à tous les coups, mais on la soupçonne de coûter cher, puisque la solution la plus courte, elle, ne s’interdit rien. Nous avons voulu mesurer ce prix. Pour cela, nous avons fait appliquer la méthode à un ordinateur, sans un seul coup perdu, sur des milliers de grilles tirées comme dans le jeu. Le résultat surprend : ce n’est pas l’ordre des étapes qui coûte des coups, c’est la façon de les enchaîner.
L’expérience
Nous avons repris les étapes de notre guide de résolution. Au 3×3, il y en a quatre : placer le 1 ; placer le 2 et le 3 ensemble ; placer la colonne du 4 et du 7 ; finir le carré du 5, du 6 et du 8, la case vide terminant en bas à droite. Au 4×4, on place le 1, le 2, puis le 3 et le 4 ensemble, de même pour la deuxième rangée, puis les paires 9 et 13, 10 et 14, et le carré final. Dès que les tuiles d’une étape sont à leur place, elles sont verrouillées.
Le programme joue ensuite chaque étape par le chemin le plus court possible, sans jamais faire bouger une tuile verrouillée. C’est le mieux que puisse faire un joueur qui pense « une étape à la fois » : il ne perd aucun coup dans l’étape en cours, mais ne regarde pas où ses manœuvres laissent les tuiles suivantes. Un coup est compté comme dans le jeu : une tuile qui glisse d’une case. Les grilles viennent de la fonction de mélange du jeu elle-même : au 3×3, nous avons pris toutes les grilles que le jeu peut servir, soit 181 439 ; au 4×4, 500 grilles dont la solution la plus courte avait déjà été calculée pour notre article sur les positions les plus difficiles, plus 5 000 autres pour le détail par étape ; au 5×5, 2 000 grilles.
Presque deux fois l’optimum au 4×4
| Grille | Solution la plus courte, moyenne | Méthode jouée étape par étape, moyenne | Écart |
|---|---|---|---|
| 3×3 (toutes les grilles) | 21,97 | 31,43 | +9,46 coups |
| 4×4 (500 grilles) | 52,58 | 96,49 | +43,90 coups |
| 5×5 (2 000 grilles) | inconnue, au moins 76,17 | 215,07 | non mesurable |
Au 3×3, la méthode jouée ainsi demande 43 % de coups de plus que la solution la plus courte ; au 4×4, 83 % de plus. Pour le 5×5, calculer la solution la plus courte de 2 000 grilles est hors de portée de notre ordinateur ; nous donnons à la place la moyenne de la distance de Manhattan, qui additionne les distances de chaque tuile à sa case et ne peut pas dépasser le vrai minimum. Ces moyennes valent pour un jeu sans détour à l’intérieur de chaque étape. Un détour ajoute en général des coups, sauf s’il prépare la suite : nous allons voir que c’est justement là que se cachent les économies. Un détail du programme pouvait fausser la mesure : quand deux chemins d’une étape ont la même longueur, il faut en choisir un. Nous avons testé deux règles de choix opposées : 31,43 contre 31,42 coups au 3×3, 96,49 contre 95,82 au 4×4. Le résultat ne tient donc pas à ce détail.
Où partent les coups
Sur les 5 000 grilles 4×4, voici ce que coûte chaque étape en moyenne :
| Étape (4×4) | Coups en moyenne |
|---|---|
| Tuile 1 | 10,41 |
| Tuile 2 | 9,34 |
| Tuiles 3 et 4 ensemble | 18,57 |
| Tuile 5 | 8,34 |
| Tuile 6 | 7,20 |
| Tuiles 7 et 8 ensemble | 15,71 |
| Colonne 9 et 13 | 13,02 |
| Colonne 10 et 14 | 9,81 |
| Carré final (11, 12, 15) | 3,21 |
| Total | 95,59 |
La première rangée absorbe à elle seule 38,32 coups, soit 40 % du total. Les fins de rangée, où deux tuiles doivent arriver ensemble, sont les étapes les plus chères prises une à une. À l’inverse, le carré final, qui paraît souvent la partie la plus délicate, ne coûte que 3,21 coups en moyenne : avec trois tuiles et la case vide sur quatre cases, les positions possibles sont peu nombreuses.
Le 3×3 calculé jusqu’au bout : l’ordre ne coûte presque rien
Reste à savoir d’où vient l’écart. Est-ce la contrainte elle-même, ranger dans cet ordre et ne plus toucher à ce qui est fait ? Ou la vue courte, qui joue chaque étape sans penser à la suivante ? Au 3×3, on peut trancher par un calcul complet. Nous avons cherché, pour chacune des 181 439 grilles, la solution la plus courte qui respecte exactement les mêmes règles : mêmes étapes, même ordre, et verrouillage dès que les tuiles d’une étape sont en place. La seule différence avec le jeu étape par étape, c’est que chaque étape est choisie en pensant à la suite. Toutes les solutions trouvées ont été rejouées coup par coup pour vérifier qu’elles respectent ces règles et rangent bien la grille.
- Jouée en pensant à la suite, la méthode demande en moyenne 22,16 coups, contre 21,97 pour la solution la plus courte sans contrainte : 0,18 coup d’écart.
- Pour 94,16 % des grilles, il existe une solution la plus courte qui suit la méthode à la lettre. L’écart maximal, sur toutes les grilles, est de 10 coups.
- Jouée étape par étape, la même méthode demande 31,43 coups : la vue courte coûte en moyenne 9,27 coups, l’ordre des étapes 0,18.
Prends la grille 2 1 3 / 4 5 6 / 8 7 _ (rangée par rangée, le tiret bas étant la case vide). Étape par étape, le programme place le 1 en 5 coups, puis il lui en faut 11 pour le 2 et le 3, 10 pour la colonne du 4 et du 7 et 6 pour le carré : 32 coups. La solution qui pense à la suite respecte le même ordre, mais elle prend 17 coups avant que le 1 arrive à sa place, en profitant de ce temps pour préparer les autres tuiles ; il ne lui reste alors que 1, 3 et 1 coups pour les trois étapes suivantes. Total : 22 coups, la solution la plus courte de cette grille. En moyenne sur toutes les grilles, la version qui pense à la suite consacre 12,81 coups à la première étape, deux fois plus que la version étape par étape (6,17), et le récupère largement ensuite.
Au 4×4 : voir plus loin rapporte la moitié de l’écart
Le même calcul complet est hors de portée au 4×4. Nous avons donc testé une version intermédiaire : chaque rangée du haut est jouée comme une seule étape, toutes ses tuiles en même temps, par le chemin le plus court ; le reste ne change pas. Ce n’est plus jouer une tuile à la fois, c’est préparer toute la rangée d’un coup d’œil.
| 4×4, 500 grilles | Moyenne | Écart avec la plus courte |
|---|---|---|
| Solution la plus courte | 52,58 | 0 |
| Rangée entière d’un coup | 74,36 | +21,77 |
| Méthode tuile par tuile | 96,49 | +43,90 |
Penser la rangée en entier fait gagner 22 coups en moyenne, la moitié de l’écart avec la solution la plus courte, et ne fait pire que sur 14 grilles sur 500. Au 3×3, la même idée fait passer la moyenne de 31,43 à 26,88 coups. Un humain ne calcule pas le chemin parfait pour quatre tuiles à la fois, mais le principe se pratique : pendant que tu amènes le 1, regarde où sont le 2, le 3 et le 4, et choisis les trajets qui les rapprochent de leur case au lieu de les repousser.
Rangée puis colonne : un petit gain qui grandit avec la grille
Le guide mentionne une variante : faire la première rangée, puis la première colonne, ce qui ramène un 5×5 à un 4×4, puis un 4×4 à un 3×3. Jouée étape par étape comme précédemment, elle fait un peu mieux. Au 4×4, sur 5 000 grilles, elle économise 1,89 coup en moyenne ; elle est meilleure sur 2 637 grilles, moins bonne sur 1 784, à égalité sur les autres. Au 5×5, sur 2 000 grilles, elle descend de 215,07 à 207,89 coups, soit 7,18 de moins, et l’emporte sur 1 263 grilles contre 650. Le gain est réel mais modeste à côté de celui qu’apporte le fait de voir plus loin.
La difficulté de la grille n’explique pas tout
Notre article sur la part de chance du classement montre que toutes les grilles ne se valent pas. C’est vrai, mais pour qui joue étape par étape, la difficulté de la grille n’explique qu’une partie du résultat : la corrélation entre la solution la plus courte d’une grille et le coût de la méthode n’est que de 0,49 au 3×3 et de 0,41 au 4×4. Sur les 500 grilles 4×4, le surcoût de la méthode va de 14 à 78 coups selon la position. Deux grilles qui demandent le même nombre minimal de coups peuvent donc coûter très différemment à la méthode jouée étape par étape : le coût d’une partie dépend de la grille, mais aussi, et largement, de la manière dont les étapes s’enchaînent sur cette grille-là.
Ce qu’il faut retenir
- L’ordre de la méthode n’est pas le problème. Au 3×3, la méthode suivie à la lettre, mais jouée en pensant à la suite, atteint la solution la plus courte sur 94 % des grilles et ne coûte que 0,18 coup de plus en moyenne.
- Ce qui coûte, c’est de jouer chaque étape isolément. Même sans aucun coup perdu, cette façon de jouer demande 31 coups en moyenne au 3×3 au lieu de 22, et 96 au 4×4 au lieu de 53.
- Accepte une première étape plus longue. Une tuile placée vite n’est pas une bonne affaire si elle laisse les suivantes loin de leur case.
- Pense par rangée, pas par tuile. Au 4×4, préparer la rangée entière vaut 22 coups en moyenne dans notre simulation.
- Ne crains pas le carré final : il coûte 3 coups en moyenne. Les coups se perdent en début de partie, dans la première rangée et dans les fins de rangée.
Pour mettre tout cela à l’épreuve sur une grille identique pour tous, essaie le défi du jour : tu n’as qu’une tentative par taille et par jour, c’est le bon moment pour lever les yeux de la tuile en cours. Le guide de résolution reste la référence pour les manœuvres elles-mêmes ; cet article dit seulement où elles coûtent le plus.