Les positions les plus difficiles du Taquin : combien de coups faut-il au pire ?
Tu termines une grille en 60 coups et tu te demandes si c’était une bonne partie. La réponse dépend d’une question simple en apparence : combien de coups fallait-il au minimum pour cette grille-là ? Et, en remontant d’un cran : existe-t-il des grilles franchement plus dures que les autres, et à quoi ressemblent-elles ?
Pour le Taquin 3×3, on peut répondre de façon totale, sans approximation : un ordinateur range les 181 440 positions solubles par nombre de coups minimal en quelques secondes. Nous l’avons fait pour cet article, avec exactement les règles du jeu du site. Pour le 4×4, l’espace est trop grand pour un calcul complet sur un ordinateur ordinaire, mais on peut résoudre de façon optimale des centaines de grilles tirées comme dans le jeu et en tirer des ordres de grandeur solides. Tous les nombres de coups de cet article sortent de ce calcul.
Deux conventions avant de compter
Premier point : ce qu’on appelle un coup. Dans notre Taquin, un coup consiste à faire glisser une tuile voisine dans la case vide, d’une seule case. C’est ce que compte le compteur affiché pendant la partie, et c’est la mesure utilisée partout ici. Certains programmes comptent autrement, par exemple en considérant qu’on peut pousser d’un seul geste toute une rangée de tuiles ; les nombres changent alors, il faut s’en souvenir en lisant d’autres sources.
Second point : la grille rangée. Chez nous, elle contient les tuiles dans l’ordre de gauche à droite et de haut en bas, la case vide étant en bas à droite. Dans la suite, une grille 3×3 s’écrit rangée par rangée, séparées par une barre oblique, avec un tiret bas pour la case vide. La grille rangée s’écrit donc 1 2 3 / 4 5 6 / 7 8 _.
Le 3×3 entièrement cartographié
La méthode est une recherche en largeur : on part de la grille rangée, on note toutes les positions atteignables en 1 coup, puis toutes les nouvelles positions atteignables en 2 coups, et ainsi de suite jusqu’à ce qu’il n’en reste plus aucune. Comme un coup se défait par le coup inverse, la distance qui sépare la grille rangée d’une position est exactement le nombre minimal de coups pour résoudre cette position. Le calcul atteint bien les 181 440 positions solubles, c’est-à-dire la moitié des 362 880 dispositions possibles des huit tuiles et du trou ; l’autre moitié est insoluble, comme l’explique notre article sur les configurations impossibles du Taquin.
Le résultat tient en trois chiffres :
- la position la plus éloignée de la solution demande 31 coups ;
- la moyenne sur toutes les positions est de 21,97 coups ;
- la moitié des positions se résolvent en 22 coups ou moins.
Voici la répartition complète, regroupée par tranches :
| Coups minimaux | Nombre de positions | Part du total |
|---|---|---|
| 0 à 9 | 420 | 0,23 % |
| 10 à 15 | 6 859 | 3,78 % |
| 16 à 19 | 30 530 | 16,83 % |
| 20 à 23 | 78 279 | 43,14 % |
| 24 à 27 | 60 459 | 33,32 % |
| 28 et 29 | 4 670 | 2,57 % |
| 30 | 221 | 0,12 % |
| 31 | 2 | 0,001 % |
Trois positions sur quatre demandent entre 20 et 27 coups. Les extrêmes sont rares dans les deux sens : à peine 4 % des grilles se règlent en 15 coups ou moins, et moins de 3 % en demandent 28 ou plus.
Une curiosité : la parité de la case vide
En triant les positions selon l’emplacement du trou, un détail saute aux yeux : quand la case vide est déjà en bas à droite, ou à deux pas de cette case, le nombre minimal de coups est toujours pair ; quand elle est à un ou trois pas, il est toujours impair. Ce n’est pas un hasard. Colorie la grille en damier : à chaque coup, la case vide change de couleur. Pour qu’elle revienne en bas à droite, le nombre de coups doit donc avoir la même parité que sa distance à cette case. Cette règle vaut pour toutes les tailles de grille, et elle donne un petit réflexe utile : une grille dont le trou est déjà à sa place ne se résout jamais en un nombre impair de coups.
Les deux positions record du 3×3
Sur 181 440 positions, seules deux demandent 31 coups :
- 8 6 7 / 2 5 4 / 3 _ 1
- 6 4 7 / 8 5 _ / 3 2 1
Elles n’ont rien de spectaculaire à première vue. Pas de motif symétrique, pas d’ordre inversé parfait. Elles partagent pourtant plusieurs traits : dans les deux, le 5 est à sa place au centre, le 1 occupe le coin opposé au sien, le 3 et le 7 ont échangé leurs coins, et le trou est à un pas de sa case finale. Juste derrière, 221 positions demandent 30 coups.
Parmi ces 221, on trouve une grille que beaucoup de joueurs imaginent comme la pire de toutes : l’ordre entièrement inversé, 8 7 6 / 5 4 3 / 2 1 _. Elle demande 30 coups : très difficile, mais pas la plus difficile. Et si l’on retourne la grille rangée d’un demi-tour, ce qui donne _ 8 7 / 6 5 4 / 3 2 1, on descend à 28 coups. L’intuition « plus c’est désordonné à l’œil, plus c’est long » fonctionne à peu près, mais elle ne désigne pas les vrais records.
Les positions trompeuses : presque rangées, et pourtant longues
L’inverse est plus surprenant et plus utile en partie. Prends la grille 2 1 3 / 4 5 6 / 8 7 _ : seules quatre tuiles sont déplacées, et chacune n’est qu’à une case de sa place. On a envie de dire « quatre ou cinq coups ». Le solveur répond 22 coups, c’est-à-dire exactement la moyenne d’une grille complètement mélangée.
La raison est mécanique. Deux tuiles voisines ne peuvent pas simplement échanger leurs places : il faut faire tourner le trou autour d’elles, en dérangeant au passage d’autres tuiles qu’il faut ensuite remettre. D’ailleurs, échanger une seule paire, par exemple 2 1 3 / 4 5 6 / 7 8 _, donne une grille insoluble ; il faut deux paires échangées pour retomber dans la bonne moitié, et chaque paire se paie cher.
Le phénomène est le même en 4×4. La grille rangée où l’on échange le 1 avec le 2 et le 14 avec le 15, soit 2 1 3 4 / 5 6 7 8 / 9 10 11 12 / 13 15 14 _, n’a que quatre tuiles déplacées d’une case. Elle demande pourtant 28 coups au minimum. C’est la situation que tu rencontres en fin de partie quand deux tuiles voisines sont « presque bonnes » mais inversées : le guide comment résoudre le Taquin explique justement comment placer les deux dernières tuiles d’une rangée ensemble pour ne jamais tomber dans ce piège.
Pourquoi la distance de Manhattan se trompe sur ces grilles
La façon la plus naturelle d’estimer la difficulté d’une grille consiste à additionner, pour chaque tuile, le nombre de cases qui la séparent de sa place en ne se déplaçant qu’horizontalement et verticalement. C’est la distance de Manhattan. Comme une tuile n’avance que d’une case par coup, cette somme ne dépasse jamais le vrai nombre de coups : c’est une borne basse.
Le calcul complet du 3×3 montre à quel point cette borne est optimiste :
- en moyenne, la distance de Manhattan vaut 14, alors que le vrai minimum vaut 21,97 ;
- elle ne tombe juste que pour 1,3 % des positions ;
- l’écart avec le vrai minimum est toujours un nombre pair, de 0 à 18 coups ;
- le pire écart, 18 coups, est atteint notamment par la grille trompeuse 2 1 3 / 4 5 6 / 8 7 _ : Manhattan annonce 4, il en faut 22.
Les deux positions record à 31 coups ont, elles, une distance de Manhattan de 21. Ce qui les rend si longues n’est donc pas seulement la distance de chaque tuile à sa place, c’est la façon dont les tuiles se gênent mutuellement.
Les conflits linéaires
Une première correction classique consiste à repérer les conflits linéaires : deux tuiles déjà dans leur bonne rangée (ou leur bonne colonne), mais dans le mauvais ordre. L’une des deux devra forcément sortir de la rangée puis y revenir, ce qui coûte au moins deux coups de plus que ce que compte Manhattan. Sur le 3×3, ajouter ces conflits fait passer l’estimation de 4 à 12 coups pour la grille 2 1 3 / 4 5 6 / 8 7 _, et de 16 à 20 pour l’ordre inversé. Mieux, mais encore loin des 22 et 30 réels. C’est pour cela que les solveurs les plus rapides utilisent des tables précalculées, appelées bases de motifs, qui mémorisent le coût exact de groupes de tuiles.
Pour toi, la leçon pratique est simple : ne juge pas une grille au nombre de tuiles mal placées. Quelques tuiles voisines inversées entre elles coûtent souvent plus cher qu’une tuile isolée très loin de sa case.
Et le 4×4 ?
Le 4×4, c’est le format par défaut du jeu, et c’est une autre échelle : plus de 10 000 milliards de positions solubles (exactement 10 461 394 944 000). Les explorer toutes est un travail de supercalculateur. Il a pourtant été mené : une recherche en largeur complète, publiée en 2005 par Richard Korf et Peter Schultze, a établi que 80 coups suffisent toujours, et qu’il existe bien des positions qui les exigent. C’est le « nombre maximal » du 4×4, l’équivalent des 31 coups du 3×3.
Ce qui intéresse davantage le joueur, c’est la difficulté des grilles qu’il reçoit réellement. Notre jeu mélange les tuiles au hasard, toutes les dispositions ayant la même chance, puis ne garde que les grilles solubles. Nous avons reproduit ce mélange à l’identique et résolu de façon optimale 600 grilles 4×4 ainsi tirées, avec un solveur IDA* guidé par des bases de motifs (une méthode qui garantit la solution la plus courte). Chaque solution trouvée a été rejouée coup par coup pour vérifier qu’elle mène bien à la grille rangée.
| Grilles 4×4 tirées comme dans le jeu | Valeur |
|---|---|
| Nombre de grilles résolues | 600 |
| Coups minimaux, moyenne | 52,4 |
| Coups minimaux, médiane | 53 |
| Grille la plus facile | 39 coups |
| Grille la plus difficile | 65 coups |
| Grilles entre 45 et 59 coups | 516 (86 %) |
| Grilles à 60 coups ou plus | 39 (6,5 %) |
| Distance de Manhattan, moyenne | 36,6 |
Une grille 4×4 du jeu demande donc en moyenne un peu plus de 52 coups au minimum, et dans plus de huit cas sur dix entre 45 et 59. La distance de Manhattan, elle, sous-estime l’effort d’environ 16 coups en moyenne, encore plus nettement qu’au 3×3. Sur les 600 grilles, aucune n’est descendue sous 39 coups ni n’a dépassé 65.
Autrement dit, la grille la plus dure de notre échantillon reste à 15 coups du record absolu de 80. Les positions à 80 coups sont si rares qu’un tirage au hasard n’a pratiquement aucune chance d’en produire une : comme au 3×3, l’essentiel des grilles se concentre autour de la moyenne.
Pour le 5×5, la grille à 24 pièces (notre guide de résolution explique comment l’aborder), l’espace compte environ 7,76 × 1024 positions solubles. Aucune exploration complète n’est envisageable, et le nombre maximal exact de coups n’y est pas connu, à notre connaissance ; seules des bornes ont été établies.
Ce que ces chiffres changent pour ta partie
Juger un score avec le bon étalon
Au 3×3, une grille du jeu demande en moyenne 22 coups au minimum, et presque jamais plus de 28. Si tu termines régulièrement autour de 60 ou 80 coups, ce n’est pas que tes grilles sont mauvaises : c’est la méthode qui coûte. Une méthode humaine qui range la grille par étapes, sans jamais défaire ce qui est placé, fait mécaniquement plus de coups que l’optimum, car elle s’interdit les raccourcis qui consistent à déranger temporairement une tuile bien placée. Au 4×4, l’étalon est d’une cinquantaine de coups pour une grille ordinaire.
Ne pas se fier à l’apparence d’une grille
Une grille « presque rangée » avec des paires inversées peut être aussi longue qu’une grille totalement mélangée, et l’ordre inversé n’est pas le pire cas. Quand deux tuiles voisines sont inversées en fin de partie, accepte de défaire un peu de travail pour les reprendre proprement : c’est souvent la voie la plus courte, et c’est exactement ce que fait le solveur sur la grille 2 1 3 / 4 5 6 / 8 7 _.
Comparer des parties entre elles
Comme toutes les grilles ne se valent pas, deux parties de même taille ne sont comparables qu’en moyenne. Une grille à 15 coups minimaux et une grille à 29 coups minimaux peuvent toutes deux tomber au 3×3, même si c’est rare. Juger sa progression sur une série de parties plutôt que sur une seule est donc plus juste.
En résumé
Le Taquin 3×3 est entièrement résolu : 181 440 positions solubles, une moyenne de 21,97 coups, 221 positions à 30 coups et seulement deux à 31, 8 6 7 / 2 5 4 / 3 _ 1 et 6 4 7 / 8 5 _ / 3 2 1. L’ordre inversé n’est pas le record, et une grille où seules deux paires de tuiles voisines sont échangées peut valoir la moyenne d’un mélange complet. Au 4×4, le pire cas est de 80 coups, mais les grilles tirées par le jeu tournent autour d’une cinquantaine. La prochaine fois que tu ouvres une grille, regarde moins le nombre de tuiles mal placées que les paires qui se gênent : c’est là que se cachent les coups.