Le taquin : les règles et la méthode

Le matériel et la position à atteindre

Le taquin classique est un cadre carré de seize cases contenant quinze tuiles numérotées de 1 à 15. La seizième case est vide, et c'est elle qui rend le jeu possible : sans elle, rien ne bougerait.

La position à atteindre est l'ordre naturel, de gauche à droite et de haut en bas, le trou se retrouvant en bas à droite.

Les tuiles dans l'ordre, et le trou en bas à droite. C'est la seule position d'arrivée : il n'y en a pas de variante acceptée.

Le jeu existe aussi en 3 sur 3 (huit tuiles) ou en 5 sur 5 (vingt-quatre tuiles). Tout ce qui suit reste vrai, y compris le résultat mathématique : seule la taille change.

Ce qu'est un coup, et ce qui n'en est pas un

Un coup consiste à faire glisser dans la case vide une tuile qui lui est adjacente par un côté : au-dessus, en dessous, à gauche ou à droite. Le résultat est que la tuile et le trou ont échangé leurs places.

Il n'y a rien d'autre. Pas de diagonale. Pas de saut par-dessus une tuile. Pas de sortie du cadre. Une tuile ne peut pas non plus « pousser » sa voisine. C'est cette pauvreté extrême qui fait tout l'intérêt du jeu : avec un seul type de coup, tu ne peux pas tricher, et chaque déplacement doit être payé par une série de déplacements préparatoires.

Selon la position du trou, tu disposes de deux coups (dans un coin), trois (sur un bord) ou quatre (au centre). Un mouvement en annule toujours un autre : ramener la tuile qui vient d'arriver, c'est revenir exactement en arrière. Le jeu ne pardonne pas, mais il n'enferme jamais non plus, du moins tant que la grille est soluble.

Pourquoi une grille sur deux est impossible

Voici le fait qui rend le taquin intéressant, et que la plupart des joueurs ignorent : si tu sors les quinze tuiles du cadre et que tu les remets au hasard, tu as une chance sur deux d'avoir fabriqué un casse-tête qu'aucun être humain, aucun ordinateur et aucune quantité de temps ne résoudront jamais. Ce n'est pas une question de difficulté. C'est une impossibilité.

Ce résultat a été démontré en 1879 par Johnson et Story, et il tient dans une idée : il existe une quantité que le jeu ne peut pas modifier.

La quantité qui ne change jamais

Prends deux mesures de la grille.

• La première est la parité de la permutation des seize cases : le nombre d'échanges de deux tuiles nécessaires pour tout remettre en ordre. Ce nombre dépend de la manière dont tu t'y prends, mais le fait qu'il soit pair ou impair, lui, ne change jamais. C'est une propriété générale des permutations.
• La seconde est la parité de la distance du trou au coin en bas à droite, comptée en cases, en additionnant le nombre de lignes et le nombre de colonnes qui l'en séparent. Pas de diagonale ici non plus : on compte comme se déplace un taxi dans une ville quadrillée.

Maintenant, regarde ce qu'un coup fait à ces deux mesures. Il échange la tuile et le trou : c'est un échange de deux éléments, donc il inverse la parité de la permutation. Et il déplace le trou d'exactement une case : donc il inverse aussi la parité de la distance. Les deux basculent en même temps, à chaque coup, sans exception.

Conséquence : leur somme, elle, garde toujours la même parité. Pair plus impair devient impair plus pair : la somme reste impaire. Tu peux jouer un million de coups, cette quantité ne bougera pas d'un pouce. C'est ce qu'on appelle un invariant.

Ce que l'invariant interdit

La position résolue a une valeur bien précise pour cet invariant. Toute position que tu peux atteindre en jouant depuis elle a forcément la même valeur, puisque aucun coup ne la modifie. Et comme le jeu est réversible, toute position depuis laquelle tu peux atteindre la solution a, elle aussi, cette valeur.

Donc : une grille dont l'invariant a l'autre valeur ne peut pas être résolue. Jamais. Pas parce qu'elle est difficile, mais parce qu'elle n'est pas dans le même monde. Les 16 factorielle façons de disposer les tuiles se répartissent en deux familles étanches de taille exactement égale, et une seule des deux contient la solution. D'où la moitié.

Le corollaire pratique

Un taquin physique que tu mélanges en faisant glisser les tuiles reste toujours soluble : tu ne fais que t'éloigner de la solution par un chemin que tu peux reparcourir à l'envers. En revanche, un taquin dont on a sorti les tuiles pour les remettre au petit bonheur est soluble une fois sur deux. C'est la raison pour laquelle des générations d'enfants se sont acharnées sur des grilles condamnées d'avance après avoir démonté le jouet.

Une version en ligne sérieuse ne peut donc pas se contenter de tirer un ordre au hasard : elle doit soit mélanger par une suite de coups légaux, soit vérifier l'invariant avant de distribuer la grille. Sans cela, un joueur sur deux se bat contre un mur.

Tout est en ordre, sauf les deux dernières tuiles, interverties. Cette position est démontrée insoluble depuis 1879 : elle appartient à l'autre famille. Loyd a promis 1000 dollars à qui la résoudrait, en toute sécurité.

La méthode : ligne par ligne, puis en colonnes

Le taquin ne se résout pas « en essayant ». Il se résout par une méthode, et cette méthode repose sur un principe unique : une zone rangée ne se retouche plus. Chaque ligne terminée réduit l'espace de travail, jusqu'à un carré final assez petit pour être traité à vue.

1. La première ligne, puis la deuxième

Tu places 1, 2, 3, 4, dans cet ordre, en te servant librement des trois lignes du dessous comme espace de manoeuvre. Une fois la ligne du haut faite, tu l'oublies : elle devient un mur. Tu recommences avec 5, 6, 7, 8 en n'utilisant plus que les deux dernières lignes.

2. Le piège des deux derniers de chaque ligne

C'est ici que la plupart des joueurs cassent tout. Tu poses le 1 et le 2 sans difficulté, puis tu poses le 3 à sa place, et là tu découvres qu'il est impossible d'amener le 4 à côté de lui sans déranger le 3. La ligne se sabote elle-même.

La parade est contre-intuitive et il faut la connaître : on ne place pas les deux derniers dans l'ordre, on les place ensemble, en position tournée. Tu amènes le 3 dans le coin en haut à droite, c'est-à-dire à la place du 4, et le 4 juste en dessous de lui. Les deux forment alors une paire verticale mal orientée. Une simple rotation du trou autour de ces deux cases les fait basculer d'un coup à leurs places définitives. La même astuce s'applique au 7 et au 8.

3. Les deux dernières lignes se traitent en colonnes

C'est le passage qui bloque le plus de monde, et pour une bonne raison : sur deux lignes, il n'y a plus de place pour manoeuvrer verticalement. Le réflexe de continuer ligne par ligne ne marche pas. Il faut changer d'axe et traiter la zone colonne par colonne : tu places le 9 et le 13 ensemble dans la première colonne, puis le 10 et le 14, avec exactement la même astuce de paire tournée que pour les fins de ligne.

4. Les six dernières cases

Il ne reste alors qu'un rectangle de deux lignes sur trois colonnes, avec cinq tuiles et le trou. À ce stade, le trou n'a plus qu'un chemin : il tourne en boucle. Les tuiles défilent comme sur un carrousel, et il suffit de tourner jusqu'à ce qu'elles tombent en place. Si elles refusent obstinément, ce n'est pas de la malchance : c'est qu'une erreur a été commise plus haut, ou que la grille était insoluble dès le départ.

5. Le repère qui recadre tout

Retiens ce chiffre : aucune grille de 15 tuiles soluble ne demande plus de 80 mouvements pour être résolue, et les positions qui exigent ce maximum se comptent sur les doigts de deux mains. La grille la plus méchante que tu verras jamais tient donc en 80 coups. Si ton compteur affiche 250, le problème n'est ni la grille, ni la malchance, ni le mélange : c'est la méthode. C'est une bonne nouvelle, parce qu'une méthode, ça s'apprend.

Un postier, un imposteur, et une prime de 1000 dollars

L'histoire du taquin est un cas d'école de paternité volée.

L'inventeur est un dénommé Noyes Palmer Chapman, receveur des postes à Canastota, dans l'État de New York. Il montre à des amis, dès 1874, un ancêtre du jeu composé de seize blocs numérotés. Il dépose une demande de brevet pour son « Block Solitaire Puzzle » le 21 février 1880. Elle est refusée, jugée trop proche d'un brevet de 1878. Le jeu devient une folie nationale aux États-Unis en 1880, et Chapman n'en tire rien.

Entre alors en scène Sam Loyd, auteur de casse-tête célèbre. Il publie un premier article sur le jeu en 1886. Puis, à partir de 1891 et jusqu'à sa mort en 1911, il affirme l'avoir inventé. C'est faux : Loyd n'a eu aucun rôle ni dans l'invention, ni dans le succès initial du jeu. Sa version a pourtant tenu bon pendant près d'un siècle, parce qu'il était un formidable vendeur.

Et il avait un argument imparable. Loyd a promis 1000 dollars, une somme considérable pour l'époque, à qui parviendrait à résoudre une grille où tout est en ordre sauf le 14 et le 15, intervertis. L'Amérique s'est acharnée dessus. Personne n'a jamais touché la prime, et pour cause : la démonstration de Johnson et Story, publiée plus de dix ans avant que Loyd ne lance son défi, établissait déjà que cette position exige de passer d'une permutation paire à une permutation impaire, ce qu'aucune suite de coups ne peut faire. Loyd promettait mille dollars pour une chose dont l'impossibilité était démontrée et publiée.

Questions fréquentes