Comment résoudre un taquin : 3x3, 4x4 et 5x5 pas à pas

Pour résoudre un taquin, termine la rangée du haut, puis celle du dessous, et continue jusqu'à ce qu'il ne reste que deux rangées ; termine ces deux-là colonne par colonne en partant de la gauche, et le dernier carré de 2×2 se résout tout seul quand tu fais tourner la case vide autour. La seule astuce à connaître concerne les deux dernières pièces de chaque rangée et de chaque colonne : elles se placent ensemble, en paire empilée, et non l'une après l'autre.

C'est toute la méthode, et elle marche aussi bien sur un 3×3 que sur un 4×4 ou un 5×5. Plus bas, tu la trouveras détaillée coup par coup, avec le test de parité qui dit si un plateau peut seulement être résolu, et le plan différent qu'il faut pour le Klotski et les puzzles d'évasion en voiture, où les pièces n'ont pas toutes la même taille. Si tu veux un plateau pour t'entraîner, joue ici : notre Sliding Puzzle gratuit tourne dans le navigateur en 3x3, 4x4 et 5x5, et chaque mélange qu'il distribue est soluble.

La règle : une seule case vide, et la moitié des mélanges sont insolubles

Un taquin, c'est un cadre carré rempli de pièces numérotées, avec un emplacement manquant. Tu fais glisser dans le trou n'importe quelle pièce qui le touche, et le but est de remettre les pièces dans l'ordre, de gauche à droite et de haut en bas, avec la case vide dans le coin en bas à droite. La version 3×3 est le jeu du 8, le 4×4 le jeu du 15 et le 5×5 le jeu du 24, d'après le nombre de pièces qu'ils contiennent.

Sors les pièces du cadre et remets-les au hasard : exactement la moitié des dispositions possibles ne pourront jamais être résolues. Les glissements ne modifient jamais une grandeur cachée appelée la parité, et tu peux la vérifier avec un crayon. Lis les pièces de gauche à droite et de haut en bas, en sautant la case vide, et compte chaque paire où un nombre plus grand passe avant un plus petit. Chacune de ces paires est une inversion.

• Largeur impaire (3×3, 5×5) : le puzzle est soluble si et seulement si le nombre d'inversions est pair.
• Largeur paire (4×4) : ajoute le numéro de la rangée où se trouve la case vide, en comptant les rangées de 1 à 4 depuis le haut. Le puzzle est soluble si et seulement si ce total est pair. (Si tu comptes les rangées depuis le bas, il te faut un total impair. Même règle, prise à l'envers.)

Un exemple concret en 3×3. Prends le plateau 1 3 _ / 4 2 5 / 7 8 6, avec la case vide en haut à droite. En le lisant, on obtient 1, 3, 4, 2, 5, 7, 8, 6. Les inversions sont 3 avant 2, 4 avant 2, 7 avant 6 et 8 avant 6 : quatre, un nombre pair, donc il est soluble. Il faut quatre coups : glisse le 3 à droite, le 2 vers le haut, le 5 à gauche et le 6 vers le haut. Prends maintenant un plateau résolu et échange le 7 et le 8. Ça fait une inversion, un nombre impair, et aucune suite de glissements ne le réparera jamais.

C'est la version 4×4 de ce piège qui a rendu le jeu du 15 célèbre. Il a fait fureur aux États-Unis en 1880, et l'auteur de casse-tête Sam Loyd a plus tard affirmé avoir offert une récompense de $1,000 pour qui, partant d'un plateau résolu où le 14 et le 15 étaient inversés, saurait les remettre en ordre. Une inversion, plus la case vide en rangée 4, ça fait 5 : impair, donc impossible. L'argent du prix n'a jamais couru le moindre risque. Tout taquin numérique correctement conçu se mélange en jouant des coups légaux depuis un plateau résolu, donc celui de ton écran a une solution. Un taquin en plastique qu'un petit frère a démonté, peut-être pas.

Le 3×3 (jeu du 8) se résout en quatre étapes

Les rangées sont numérotées depuis le haut et les colonnes depuis la gauche. « Verrouiller » veut dire qu'à partir de là, la case vide ne repasse plus jamais par ces cases.

1. La pièce 1 à sa place. Fais tourner la case vide pour amener le 1 dans le coin en haut à gauche. Verrouille-le.
2. Les pièces 2 et 3 en paire empilée. Place le 2 dans le coin en haut à droite (la case du 3, pas la sienne) et le 3 juste en dessous, en rangée 2, colonne 3. Amène la case vide au milieu de la rangée du haut en passant par la rangée 2, jamais par le coin. Glisse le 2 à gauche, puis le 3 vers le haut. La rangée du haut est faite. Verrouille-la.
3. Les pièces 4 et 7 en paire empilée, couchée sur le côté. Place le 7 dans la case du 4 (rangée 2, colonne 1) et le 4 juste à sa droite, au centre. Amène la case vide dans le coin en bas à gauche par la rangée du bas. Glisse le 7 vers le bas, puis le 4 à gauche. La colonne de gauche est faite. Verrouille-la.
4. Les pièces 5, 6 et 8 : la rotation. Il reste un carré de 2×2 avec trois pièces et la case vide. Fais tourner la case vide autour, toujours dans le même sens, et les trois pièces défilent jusqu'à se mettre en place. Dans le bon sens, ça ne prend jamais plus de six coups ; si le premier tour ne mène nulle part, repars dans l'autre sens.

Pourquoi la paire empilée ? Si tu places le 2 en premier, le seul chemin du 3 vers le coin passe par la case du 2, donc placer le 3 éjecte le 2. En les empilant d'abord puis en les faisant pivoter, les deux arrivent en deux glissements. La plupart des gens essaient plusieurs fois de les placer une par une avant d'y croire. Nous, encore plus de fois que la moyenne.

Le 4×4 (jeu du 15) : deux rangées, deux colonnes, puis une rotation

Le jeu du 15 suit le même plan, avec une étape de plus. Résous la rangée 1 (pièces 1 à 4) et la rangée 2 (5 à 8) comme des rangées, puis les deux rangées du bas colonne par colonne : 9 et 13, puis 10 et 14, puis fais tourner 11, 12 et 15 jusqu'à leur place dans le dernier carré de 2×2. Dans chaque rangée, les deux premières pièces sont faciles : amène-les une par une. Seule la dernière paire demande l'astuce.

Les deux dernières pièces d'une rangée, coup par coup

Voici la manœuvre pour la rangée 1, avec les pièces 1 et 2 déjà en place et verrouillées.

1. Commence par écarter la pièce 4. Si le 4 est en rangée 1 ou 2, descends-le en rangée 3 ou plus bas. Ça l'empêche de dériver vers la mauvaise case à l'étape 2.
2. Place la pièce 3 dans le coin en haut à droite (rangée 1, colonne 4), qui est la case du 4, pas celle du 3.
3. Amène la pièce 4 juste en dessous (rangée 2, colonne 4), en ne déplaçant que des pièces des rangées 2 à 4 pour que le 3 reste dans son coin.
4. Amène la case vide en rangée 2, colonne 3, à côté du 4, toujours sans toucher à la rangée 1. Puis fais descendre dans la case vide la pièce qui se trouve en rangée 1, colonne 3. La case vide est maintenant dans la case du 3, avec le 3 à sa droite et le 4 sous le 3.
5. Glisse le 3 à gauche. Glisse le 4 vers le haut. La rangée 1 est terminée. Verrouille-la.

La rangée 2 se fait de la même façon : le 5 et le 6 entrent un par un, puis le 7 va en rangée 2, colonne 4, avec le 8 en dessous en rangée 3, colonne 4, la case vide en rangée 2, colonne 3, et les deux mêmes glissements : le 7 à gauche, le 8 vers le haut.

Les deux rangées du bas, une colonne à la fois

Une fois les rangées 1 et 2 verrouillées, il te reste deux rangées de quatre : 9, 10, 11, 12 au-dessus de 13, 14, 15 et de la case vide. Travailler par rangées ne marche plus ici, faute de rangée libre où garer des pièces, donc tu avances par colonnes, avec la même astuce de paire tournée sur le côté.

1. Colonne 1 (pièces 9 et 13). Place le 13 dans la case du 9 (rangée 3, colonne 1) et le 9 juste à sa droite (rangée 3, colonne 2). Amène la case vide le long de la rangée 4 jusqu'en rangée 4, colonne 1. Glisse le 13 vers le bas, puis le 9 à gauche. Verrouille la colonne.
2. Colonne 2 (pièces 10 et 14). Même chose une colonne plus loin : le 14 en rangée 3, colonne 2, le 10 en rangée 3, colonne 3, la case vide en rangée 4, colonne 2. Glisse le 14 vers le bas, le 10 à gauche. Verrouille-la.
3. Le dernier carré de 2×2 (11, 12 et 15). Fais tourner la case vide autour du carré jusqu'à ce que les trois pièces soient en place, exactement comme sur le 3×3. Si le mélange était légal, elles le seront.

Cette méthode est fiable, pas courte. Un ordinateur qui cherche le chemin le plus court n'a jamais besoin de plus de 80 coups d'une seule pièce sur n'importe quel jeu du 15, et seules 17 positions en demandent 80. Rangée par rangée, il en faut davantage, mais tu peux le faire sans t'arrêter pour réfléchir, et pour un humain, ça compte beaucoup plus que le nombre de coups.

Le 5×5 (jeu du 24) est un 4×4 avec une rangée et une colonne en plus

Chaque grand plateau se ramène à celui de la taille en dessous. Sur un 5×5, résous la rangée 1 (pièces 1 à 5, avec le 4 et le 5 en paire empilée), puis la colonne de gauche en dessous (6, 11, 16 et 21, avec le 16 et le 21 en paire couchée : le 21 dans la case du 16, le 16 à sa droite, la case vide en dessous, glisse le 21 vers le bas et le 16 à gauche). Verrouille les deux, et il te reste un 4×4 composé des pièces 7 à 10, 12 à 15, 17 à 20 et 22 à 24. Résous-le exactement comme plus haut, en lisant les numéros comme des positions plutôt que comme 1 à 15.

Tu peux aussi continuer rangée par rangée jusqu'à la rangée 3, puis faire les deux rangées du bas par colonnes ; les deux chemins finissent par la même rotation du carré de 2×2. Le 5×5 compte environ 7,76×10²⁴ dispositions atteignables, et personne n'a encore établi le nombre maximal de coups que l'une d'elles peut exiger. Les bornes les plus récentes que nous avons trouvées, qui datent de 2016, le situent entre 152 et 205 coups d'une seule pièce.

Le Klotski et les puzzles d'évasion en voiture demandent une autre méthode

La méthode rangée par rangée ne marche que si toutes les pièces ont la même taille. Le Klotski, et toute la famille des puzzles à blocs coulissants à laquelle il appartient, mélange des pièces de formes différentes, et il n'y a aucune rangée à terminer puisque rien n'a de place numérotée. Une seule pièce compte : celle que tu essaies de faire sortir.

La position de départ classique du Klotski est un plateau de 4×5 qui contient dix pièces : un gros bloc de 2×2 en haut au milieu, un bloc de 2×1 couché juste dessous, deux petits carrés de 1×1 sous celui-ci, et de chaque côté deux blocs de 1×2 debout avec un carré de 1×1 en bas. Les deux cases vides sont côte à côte en bas au milieu. Le but est d'amener le bloc de 2×2 en bas au milieu, puis de le faire sortir par l'ouverture du cadre. En Chine, le même puzzle s'appelle Huarong Dao, et le gros bloc y joue le seigneur de guerre Cao Cao en pleine fuite, ce qui fait beaucoup de scénario pour quelques bouts de bois.

1. Planifie d'abord le trajet de la pièce cible. Avant de bouger quoi que ce soit, trace case par case le chemin que le gros bloc (ou la voiture en fuite) doit suivre jusqu'à la sortie.
2. Remonte depuis la sortie. Pour la prochaine étape de ce chemin, demande-toi ce qui doit être vide, quelle pièce gêne et où cette pièce peut aller. Puis pose la même question pour ce qui gêne cette pièce-là. Cette chaîne, c'est le vrai puzzle.
3. Garde les deux cases vides ensemble dans le Klotski. Un bloc vertical de 1×2 ne peut se déplacer sur le côté que dans deux cases vides superposées, le bloc horizontal de 2×1 en demande deux côte à côte pour monter ou descendre, et le gros bloc en a toujours besoin de deux. Séparer les cases vides immobilise la moitié des pièces.
4. Compte les coups en pièces déplacées, pas en cases. Au Klotski, une pièce qui glisse jusqu'à n'importe quel endroit qu'elle peut atteindre compte pour un coup, et selon ce décompte, le départ classique en demande au moins 81. Un plan du genre « ce bloc contre le mur de gauche » est plus facile à garder en tête qu'une liste de pas élémentaires.

Les puzzles de voitures coulissantes, la famille Rush Hour, ajoutent une règle : chaque véhicule est bloqué dans sa propre voie, donc une voiture placée en travers du plateau ne peut aller qu'à gauche ou à droite. La chaîne à rebours devient encore plus utile, puisque chaque gêneur n'a que quelques endroits où finir. Une fois que ça a fait tilt, progresser aux puzzles façon Rush Hour consiste à réduire le nombre de coups, ce qui est une compétence à part.

3x3, 4x4, 5x5 et Klotski en un coup d'œil

Les erreurs fréquentes qui empêchent de finir un plateau

• Placer une par une les deux dernières pièces d'une rangée. La seconde éjecte toujours la première. Empile-les et fais-les pivoter.
• Laisser la case vide revenir dans une rangée terminée. Chaque passage là-haut défait ton travail. Si un chemin l'exige, trouve-en un autre.
• Traiter les deux rangées du bas comme des rangées. Il n'y a nulle part où garer une pièce. Passe aux colonnes quand il reste deux rangées.
• Traiter le dernier 2×2 comme trois pièces séparées. C'est une seule rotation. Fais le tour, et si le premier tour ne donne rien, repars dans l'autre sens.
• Se tromper dans le calcul de la parité. Ne compte pas la case vide comme une pièce et, sur un 4×4, n'oublie pas d'ajouter la rangée de la case vide.
• Séparer les deux cases vides au Klotski. Les gros blocs ont besoin des deux, côte à côte, pour bouger tout court.

Où jouer au taquin en ligne : notre jeu du 15 gratuit, puis Car Parking

Le plateau idéal pour la méthode ci-dessus, c'est notre Sliding Puzzle, gratuit dans le navigateur, sans téléchargement ni inscription. Choisis un 3×3, un 4×4 ou un 5×5, avec des pièces numérotées ou une image de casse, et la parité de chaque mélange est vérifiée avant que tu le voies : tu ne tomberas jamais sur la moitié impossible. L'annulation est illimitée, et le jeu garde ton meilleur nombre de coups et ton meilleur temps pour chaque taille. Sa limite : ces records sont stockés dans ton navigateur, donc effacer les données du site ou jouer en navigation privée les efface.

Pour le côté Klotski et Rush Hour de la famille, essaie Car Parking : un parking de 6×6, une voiture dorée coincée par la circulation, et chaque véhicule bloqué dans sa propre voie. Un coup, c'est un véhicule qui se gare ailleurs, quelle que soit la distance parcourue, et chacun des 240 niveaux affiche un par, la solution la plus courte trouvée par notre solveur, avec trois indices par niveau. Il entraîne la méthode qui remonte depuis la sortie plutôt que celle de la progression rangée par rangée. Getaway Garage déplace tous les véhicules à la fois à chaque balayage et fait disparaître les trios de même couleur, ce qui en fait encore un autre puzzle, et notre histoire des puzzles d'embouteillage commence par la folie du jeu du 15 si tu veux le contexte.

La règle de décision tient en deux lignes. Si toutes les pièces ont la même taille, termine les rangées depuis le haut, passe aux colonnes pour les deux dernières rangées et fais tourner le dernier carré. Si les pièces diffèrent, choisis la seule pièce qui doit s'échapper et planifie à rebours depuis la sortie. Teste la première sur un Sliding Puzzle en 4×4 et la seconde dans Car Parking, tous deux gratuits dans ton navigateur.