Le Taquin et la topologie : pourquoi la parité détermine si le puzzle est soluble
Vous prenez un Taquin, vous mélangez les pièces au hasard, et vous essayez de le résoudre. Après une heure de tentatives infructueuses, un doute s’installe : et si cette configuration était tout simplement impossible ? Ce doute n’est pas de la paranoia. La moitié exacte de toutes les configurations possibles du Taquin sont effectivement insolubles. Et la raison de cette impossibilité plonge ses racines dans l’un des domaines les plus élégants des mathématiques : la topologie et la théorie des permutations.
Permutations : l’ordre caché derrière le désordre
Avant de plonger dans la topologie, il faut comprendre un concept fondamental : la permutation. Une permutation est simplement un réarrangement d’éléments. Prenez les nombres 1, 2, 3. Vous pouvez les arranger de six manières différentes : 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1. Chacun de ces arrangements est une permutation.
Pour le Taquin classique à 15 pièces, on parle de permutations de 15 éléments. Le nombre total de permutations possibles est 15 factorielle (noté 15!), soit 1 307 674 368 000 - plus de mille milliards d’arrangements. Mais voici le point crucial : chaque permutation possède une parité, et cette parité détermine si le Taquin est soluble ou non.
La parité d’une permutation se définit par le nombre de transpositions nécessaires pour revenir à l’ordre initial. Une transposition est l’échange de deux éléments. Si vous avez besoin d’un nombre pair de transpositions, la permutation est paire. Si le nombre est impair, la permutation est impaire. Et cette distinction ne dépend pas du chemin choisi : quelle que soit la séquence de transpositions que vous utilisez, la parité reste la même.
La parité au cœur du Taquin
Voici le théorème fondamental du Taquin : une configuration est soluble si et seulement si la permutation des pièces et la position de la case vide ont la même parité. Plus précisément, pour un Taquin 4×4 avec la case vide en position finale (coin bas-droit), la configuration est soluble quand la permutation des 15 pièces est paire.
Pourquoi ? Parce que chaque déplacement de la case vide correspond à une transposition - l’échange entre la case vide et la pièce adjacente. Quand la case vide fait un aller-retour (haut puis bas, ou gauche puis droite), elle effectue deux transpositions qui s’annulent. Pour revenir à sa position d’origine, la case vide doit parcourir un nombre pair de déplacements verticaux et un nombre pair de déplacements horizontaux - donc un nombre pair de transpositions au total.
Cela signifie que la permutation finale (l’ordre résolu) ne peut être atteinte que par un nombre pair de transpositions de pièces. Si la permutation initiale est impaire, aucune séquence de mouvements ne pourra la transformer en la permutation identité (l’ordre résolu), car chaque mouvement légal préserve la parité. Comme le détaille notre article sur les configurations insolubles du Taquin, cette propriété est absolue : aucune astuce, aucune habileté ne peut contourner la barrière de parité.
L’arnaque de Sam Loyd : la preuve par l’histoire
Cette propriété mathématique est au cœur de l’une des plus célèbres arnaques de l’histoire des puzzles. En 1880, le créateur de jeux américain Sam Loyd a offert un prix de 1 000 dollars à quiconque résoudrait un Taquin 4×4 où les pièces 14 et 15 étaient inversées. L’inversion de deux pièces adjacentes crée une permutation impaire à partir d’une permutation paire - le puzzle était mathématiquement impossible.
Des milliers de personnes ont tenté leur chance. Personne n’a jamais réclamé le prix, non par manque d’ingéniosité, mais parce que les lois de la topologie l’interdisaient. Loyd le savait parfaitement - son « défi » était un coup de génie marketing fondé sur un théorème mathématique.
La topologie entre en scène
Où la topologie intervient-elle dans tout cela ? La topologie est la branche des mathématiques qui étudie les propriétés qui ne changent pas quand on déforme un objet. Un anneau et une tasse de café sont topologiquement équivalents (tous deux ont un trou), mais un anneau et une sphère ne le sont pas.
Le lien avec le Taquin vient du concept d’espace des configurations. Imaginez chaque état possible du Taquin comme un point dans un espace abstrait. Deux points sont connectés si l’on peut passer de l’un à l’autre par un seul déplacement de pièce. L’ensemble de ces points et connexions forme un graphe - et les propriétés topologiques de ce graphe déterminent ce qui est atteignable et ce qui ne l’est pas.
Le résultat topologique fondamental est que ce graphe se divise en exactement deux composantes connexes de taille égale. Une composante contient toutes les configurations paires, l’autre toutes les configurations impaires. Aucun chemin ne relie les deux composantes - c’est comme deux îles séparées par un océan infranchissable. La configuration résolue se trouve dans la composante paire, donc seules les configurations paires peuvent l’atteindre.
Compter les inversions : la méthode pratique
La théorie est élégante, mais comment vérifier concrètement si un Taquin est soluble ? La méthode repose sur le comptage des inversions. Une inversion se produit quand une pièce de numéro supérieur précède une pièce de numéro inférieur dans l’ordre de lecture (de gauche à droite, de haut en bas).
Pour un Taquin 4×4, la règle est :
- Comptez le nombre total d’inversions parmi les 15 pièces
- Ajoutez le numéro de la rangée (en partant du bas) où se trouve la case vide
- Si la somme est paire, le puzzle est soluble
- Si la somme est impaire, le puzzle est insoluble
Prenons un exemple simple avec un Taquin 3×3 (8 pièces). La configuration 1-2-3-4-5-6-8-7 (les pièces 7 et 8 sont inversées) contient exactement une inversion : le 8 précède le 7. Un nombre impair d’inversions avec la case vide en position finale : insoluble. Vous pourrez pousser les pièces pendant des heures, la solution n’existe pas.
Les versions numériques du puzzle, comme les puzzles de type Sudoku en ligne, utilisent cette vérification automatiquement pour ne générer que des configurations solubles - un avantage considérable par rapport au mélange manuel.
Le groupe alterné : la structure mathématique profonde
Pour les amateurs de mathématiques, la structure qui sous-tend le Taquin est le groupe alterné An. Le groupe symétrique S15 contient toutes les permutations possibles de 15 éléments. Le groupe alterné A15 n’en contient que la moitié : les permutations paires. Et c’est précisément A15 qui correspond aux configurations solubles du Taquin.
Cette structure de groupe a des conséquences profondes. Elle signifie que l’ensemble des configurations solubles est clos sous la composition : si vous appliquez deux séquences de mouvements légaux l’une après l’autre, le résultat est toujours une configuration soluble. C’est la raison pour laquelle vous ne pouvez jamais « casser » un Taquin soluble en jouant normalement : chaque mouvement légal préserve la solubilité.
Le groupe alterné possède aussi la propriété d’être simple pour n ≥ 5 (au sens de la théorie des groupes : il ne contient aucun sous-groupe normal non trivial). Cette simplicité algébrique garantit que la division en deux composantes est irréductible : il n’y a pas de subdivision plus fine qui distinguerait des sous-classes de configurations solubles.
Au-delà du 15-puzzle : généralisations
Le résultat de parité se généralise à toutes les tailles de Taquin rectangulaires. Pour un Taquin de largeur impaire (3×3, 5×5...), seul le nombre d’inversions compte : il doit être pair. Pour un Taquin de largeur paire (4×4, 6×6...), il faut également prendre en compte la position de la case vide.
Plus surprenant, le même type de raisonnement topologique s’applique à d’autres puzzles. Le Rubik’s Cube obéit à des contraintes similaires : sur les 43 trillions de configurations possibles, seul un douzième est atteignable par des mouvements légaux. La raison est la même : la parité des permutations et l’orientation des pièces créent des barrières topologiques infranchissables.
Le Taquin, dans sa simplicité apparente, est donc une porte d’entrée vers certains des concepts les plus profonds des mathématiques. Chaque pièce que vous glissez est un mouvement dans un espace topologique. Chaque résolution est un chemin dans un graphe aux milliards de nœuds. Et chaque configuration insoluble est la preuve tangible qu’en mathématiques, certaines frontières sont absolues et inviolables - aussi frustrantes que cela puisse être quand on a passé une heure à essayer.