Le Taquin et la théorie des permutations : pourquoi la moitié des configurations sont impossibles
Vous avez peut-être déjà eu cette intuition frustrante : certaines configurations du Taquin semblent impossibles à résoudre, peu importe le temps passé. Ce n’est pas un manque de talent - c’est un fait mathématique. Exactement la moitié de toutes les configurations possibles du Taquin sont insolubles. Derrière cette propriété se cache un concept élégant : la parité des permutations.
Qu’est-ce qu’une permutation ?
En mathématiques, une permutation est un réarrangement d’éléments. Prenons un Taquin 3×3 classique avec les pièces numérotées de 1 à 8 et une case vide. La configuration résolue est (1, 2, 3, 4, 5, 6, 7, 8). Toute autre disposition des pièces est une permutation de cet état initial.
Pour un Taquin 3×3, il existe 9! = 362 880 façons d’arranger les 8 pièces et la case vide. C’est un nombre considérable. Mais la moitié seulement - 181 440 - sont accessibles depuis l’état résolu.
La notion de parité
Chaque permutation peut être décomposée en une série de transpositions - des échanges de deux éléments. Par exemple, pour passer de (1, 2, 3) à (3, 1, 2), on peut effectuer deux transpositions : échanger 1 et 3 (donnant 3, 2, 1), puis échanger 2 et 1 (donnant 3, 1, 2).
Le nombre de transpositions nécessaires peut varier, mais sa parité (pair ou impair) est toujours la même pour une permutation donnée. C’est un théorème fondamental de l’algèbre :
- Une permutation paire nécessite un nombre pair de transpositions
- Une permutation impaire nécessite un nombre impair de transpositions
L’identité (la configuration résolue) est une permutation paire (zéro transposition).
Le lien avec le Taquin
Quand vous déplacez une pièce dans le Taquin, vous ne faites pas une simple transposition - vous échangez la pièce avec la case vide. Chaque mouvement est donc une transposition entre une pièce et la position vide.
L’invariant de parité
Voici la clé : pour ramener la case vide à sa position d’origine, elle doit parcourir un nombre de cases dont la parité dépend de sa position. Plus précisément, si la case vide revient à son point de départ, le nombre total de mouvements de la case vide a une certaine parité.
L’invariant combine deux éléments :
- La parité de la permutation des pièces numérotées
- La parité de la distance de Manhattan de la case vide par rapport à sa position cible
Pour qu’une configuration soit soluble, la somme de ces deux parités doit être paire. C’est cette contrainte qui élimine exactement la moitié des configurations.
Un exemple concret
Considérons un Taquin 3×3 où seules les pièces 1 et 2 sont inversées, toutes les autres étant à leur place, et la case vide est en position finale. L’échange de 1 et 2 est une unique transposition - c’est une permutation impaire. La case vide est déjà à sa position : parité paire (distance 0). Somme : impair + pair = impair. Configuration impossible !
Vous pouvez passer des heures à essayer : jamais vous ne réussirez à résoudre cette configuration sans démonter le puzzle. C’est mathématiquement prouvé.
La formule de vérification
Pour vérifier si une configuration est soluble, on calcule le nombre d’inversions. Une inversion est une paire de pièces (a, b) où a apparaît avant b dans la configuration mais a > b dans l’ordre naturel.
Pour un Taquin de largeur impaire (comme le 3×3) :
- Si le nombre d’inversions est pair, la configuration est soluble
- Si le nombre d’inversions est impair, elle est insoluble
Pour un Taquin de largeur paire (comme le 4×4), la règle intègre aussi la ligne de la case vide :
- Nombre d’inversions + ligne de la case vide (comptée depuis le bas) doit être impair
L’arnaque de Sam Loyd revisitée
En 1880, le célèbre créateur de puzzles Sam Loyd proposa un défi : résoudre un Taquin 4×4 avec les pièces 14 et 15 inversées, offrant 1 000 dollars de récompense. Grâce à la théorie des permutations, on comprend pourquoi il ne risquait rien : cette unique transposition crée une permutation impaire, rendant le puzzle mathématiquement impossible.
Ce n’était pas un défi - c’était une démonstration involontaire d’algèbre abstraite, des décennies avant que la théorie ne soit formalisée dans ce contexte.
Pourquoi exactement la moitié ?
Le groupe des permutations de n éléments (noté Sn) se divise en deux sous-ensembles de taille égale :
- Le groupe alterné An : toutes les permutations paires
- Son complémentaire : toutes les permutations impaires
Comme les mouvements du Taquin ne peuvent atteindre que les configurations d’une seule parité, exactement la moitié de l’espace est inaccessible. Ce n’est pas un hasard ni une approximation - c’est une conséquence directe de la structure algébrique du problème.
Implications pour les jeux numériques
Les développeurs de jeux de Taquin connaissent bien ce problème. Pour garantir une configuration soluble, deux approches sont possibles :
- Mélanger depuis l’état résolu : en effectuant des mouvements aléatoires depuis la position finale, on reste forcément dans l’espace des configurations solubles
- Vérifier la parité : générer une configuration aléatoire, calculer les inversions, et corriger si nécessaire (une seule transposition suffit pour changer la parité)
Au-delà du Taquin
La théorie des permutations ne s’applique pas qu’au Taquin. Le Rubik’s Cube obéit à des contraintes similaires (mais plus complexes). Les puzzles de type 2048 utilisent d’autres principes mathématiques, mais partagent cette idée que l’espace des états possibles est structuré par des règles cachées.
La prochaine fois que vous mélangez un Taquin à la main et qu’il vous semble impossible, souvenez-vous : il y a une chance sur deux que ce soit le cas. Et ce n’est pas un défaut - c’est une propriété mathématique profonde, élégante et définitive.