Dans une boîte carrée, 15 carreaux numérotés de 1 à 15 sont disposés. La boîte est prévue pour 16, si bien qu'il reste une place libre, permettant de faire coulisser les carreaux. A la fin du XIXe siècle, le puzzliste Sam Loyd proposait 1000 $ à quiconque réussirait à résoudre le puzzle à partir d'une position de départ ayant l'air scandaleusement simple. Le prix n'aura jamais été réclamé, et pour cause : le problème est impossible !

Sam_Loyd___The_14_15_Puzzle_in_Puzzleland
Illustration de Sam Loyd illustrant le 15-puzzle dans sa Cyclopedia of 5000 Puzzles

Dans ses versions classiques, le puzzle se présente sous la forme de jetons numérotés à disposer plus ou moins aléatoirement que l'on cherchera à réorganiser. Dans ses versions plus modernes, on cherche à retrouver une chouette illustration d'une bouteille de coca ou d'un mignon petit esquimau. Le principe reste toujours le même : il faut faire glisser des pièces pour leur faire atteindre la place qui leur est due.

taquin_resolu
Un taquin résolu : le graal du taquinophile

Ce casse-tête, c'est le taquin (alias 15-puzzle, gem puzzle, carré mystique, pousse-pousse...), qui réveille mes vieux souvenirs de taquinophilie (je disposais à la grande époque d'une collection de 2 taquins, incluant le taquin Walibi et le taquin musée des JO de Lausanne)... Même si c'est Sam Loyd qui en a revendiqué la paternité jusqu'à sa mort, on sait  maintenant depuis quelques années que l'invention est en fait l'œuvre de Noyes Chapman, receveur des postes de New-York, qui l'a créé dans les années 1870 et a déposé son brevet en 1880.

Les configurations impaires sont insolubles...

taquin_LoydLe problème de Loyd demandait à inverser exactement deux carreaux, en l'occurrence le 14 et le 15. Le problème se relève impossible est impossible à résoudre, ce qui demande un brin de théorie des permutations pour être comprise. Dans la modélisation du jeu, on considère que le jeu est constitué de 16 carreaux, dont un "vide". Un taquin mélangé, c'est alors une permutation des 16 blocs. Par exemple, la permutation ci-contre est la permutation "le 14 est à la place du 15, le 15 est à la place du 14".

Les mouvements autorisés dans le jeu sont des transpositions : ils échangent exactement deux carreaux (en l'occurrence, un carreau vide et un carreau adjacent). Quand on effectue plusieurs mouvement les uns à la suite des autres, on procède à une permutations des 16 blocs. Résoudre le puzzle, c'est trouver une suite de transpositions autorisées qui correspond à la permutation transformant les blocs mélangés en blocs rangés.

La théorie des permutations nous dit que toute permutation peut s'écrire comme une suite de transpositions (par exemple, pour permuter [A,B,C] en [B,C,A], on peut commencer par échanger A avec B, puis A avec C). On dit qu'une permutation est paire si elle peut s'écrire avec un nombre pair de transpositions, et qu'elle est impaire sinon (une permutation est soit paire, soit impaire).
Dans le cas du taquin, une configuration est dite paire si on peut la trouver depuis la configuration résolue en échangeant des carreau deux à deux (vide ou non) un nombre pair de fois (et impaire, sinon).

Si l'on veut que le carreau blanc revient à la place qui lui est due (en bas à droite), il faudra forcément faire un nombre pair de mouvements. La permutation des blocs que l'on obtient en faisant voyager la case blanche sera donc une permutation paire. La permutation que l'on cherche à obtenir, c'est la permutation échangeant seulement 14 et 15 : c'est une transposition, qui est impaire. Une permutation ne pouvant pas être à la fois paire et impaire, il est impossible d'échanger le carreau 14 et le carreau 15 avec seulement les mouvements autorisés.

Ceci permet de dire que toutes les configurations impaires (qui correspondent à des permutations impaires) sont des configurations insolubles. Exemple en image :

taquin_impossible

La configuration juste au-dessus est impossible ! Pour le montrer, on va plutôt utiliser les notations habituelles de la théorie, et admettre quelques théorèmes. On peut écrire la permutation des blocs sous la forme matricielle suivante :

permutation_taquin
On peut lire "le 1 est à la place du 6, le 2 est à la place du 1, le 3 est à la place du 7 ..."

On peut lire ça autrement, en disant : " le 1 est la place du 6, qui est à la place du 3, qui est à la place du 7 qui est (...) à la place du 1", "le 9 est à la place du 15, qui est (...) à la place du 9". On écrit ça sous la forme :

permutation_taquin2

Ces parenthèse sont appelés cycles : on a ici écrit la permutation sous la forme d'un produit de 2 cycles, de longueur 9 et 6. C'est cette écriture qui permet, moyennant quelques théorèmes sur les permutation, d'en déterminer la parité. En l'occurrence, un cycle de longueur n est pair si n est impair, et vice-versa. Le cycle (1 6 3 7 8 5 12 4 2) est donc pair, et le cycle (9 15 14 10 13 11) est impair. Chez les permutations, les parités s'additionnent : pair + impair = impair. Notre permutation est impaire, si bien que le puzzle est ici impossible à résoudre.

Cela dit, le puzzle de Loyd peut être résolu si l'on ne demande plus à ce que le blanc soit au final en bas à droite. La configuration [0,1,2,3;4,5,6,7;8,9,10,11;12,13,14,15] est également une configuration impaire : elle est donc accessible depuis la position où le 14 et le 15 sont inversés...

...et les configurations paires sont solubles.

Tout ceci permet de connaître les configurations du taquin que l'on ne peut pas résoudre, mais ne dit absolument rien sur celle que l'on peut résoudre. En fait, on peut montrer que les configurations impaires sont les seules configurations impossibles. (une configuration est faisable si et seulement si elle est paire). Les deux résultats sont tombés en 1879, sous la plume de W.W. Johnson et W.E. Story. Le premier a montré pourquoi les configurations impaires sont impossibles à résoudre, et le deuxième a montré pourquoi ce sont les configurations paires qui sont résolubles.

Même si le sens direct est plutôt facile à démontrer, il a fallu attendre bien longtemps avant de trouver une démonstration à peu près correcte de sa réciproque. Celle fournie par Story en 1879 n'est pas très claire, et les nombreux mathématiciens qui sont passés derrière n'ont pas réussi à rendre la chose plus limpide. Herstein et Kaplansky écrivent en 1978 à ce sujet que "aucune preuve vraiment simple ne semble être connue". En 1999, A. Archer apporte une démonstration qui semble mettre tout le monde d'accord, en généralisant au passage le problème de la résolubilité d'un taquin sur un graphe quelconque (le problème du déplacement des étiquettes des nœuds). La démonstration de Archer consiste simplement à montrer que transpositions légales du taquin engendre le groupe A16.

Finalement, sur les 16! (=20 922 789 888 000, ie "21 billions de") façons de ranger 15 carreaux dans la boîte carrée, seule la moitié sont des taquins résolubles. Ce qui laisse toute de même 10 téras de taquins 4x4 différents. Et c'est ici qu'il faut dire que le nombre de Dieu du taquin 4x4 est 80 : tout taquin peut être résolu en moins de 80 déplacements...

Miaouss_taquin
Le taquin Miaouss : une pièce de collection...

 

 


Sources :
15-puzzle, chez Wolfram
La démonstration de la réciproque de Archer, plutôt accessible pour n'importe quel étudiant ayant déjà rencontré les groupes An, de novembre 1999.