Le Taquin et la théorie des groupes : quand l’algèbre structure le puzzle
Derrière les pièces glissantes du Taquin se cache une structure mathématique d’une élégance remarquable. La théorie des groupes, branche fondamentale de l’algèbre abstraite, explique non seulement pourquoi certaines configurations sont impossibles à résoudre, mais révèle aussi la symétrie cachée de l’univers des positions du Taquin. Ce n’est pas un hasard si les mathématiques du Taquin fascinent les algébristes depuis plus d’un siècle.
Qu’est-ce qu’un groupe en mathématiques ?
Un groupe est l’une des structures les plus fondamentales des mathématiques. C’est un ensemble muni d’une opération (comme la composition de mouvements) qui satisfait quatre propriétés :
- Fermeture : enchaîner deux mouvements valides produit toujours un mouvement valide
- Élément neutre : il existe un « mouvement » qui ne change rien (ne pas bouger)
- Inverse : chaque séquence de mouvements peut être annulée par une séquence inverse
- Associativité : l’ordre de regroupement des mouvements n’affecte pas le résultat final
Les mouvements du Taquin satisfont exactement ces quatre propriétés. Chaque séquence de glissements peut être composée, inversée et regroupée librement. Le Taquin forme donc naturellement un groupe - et pas n’importe lequel.
Le groupe symétrique Sn : l’espace de toutes les permutations
Pour un Taquin 3×3 avec 8 pièces numérotées, l’ensemble de toutes les dispositions possibles des pièces forme le groupe symétrique S8. Ce groupe contient 8! = 40 320 permutations (en fixant la position de la case vide). Chaque permutation est une façon de réarranger les 8 pièces.
Mais voici le point crucial : les mouvements du Taquin ne permettent pas d’atteindre toutes ces permutations. Depuis la configuration résolue, seule la moitié de S8 est accessible. Et cette moitié porte un nom précis : le groupe alterné A8.
Le groupe alterné An : la moitié accessible
Toute permutation peut être décomposée en une série de transpositions - des échanges de deux éléments. Le nombre de transpositions nécessaires peut varier, mais sa parité est invariante : une permutation est toujours soit paire (nombre pair de transpositions), soit impaire.
Cette propriété s’appelle la signature d’une permutation. C’est un concept fondamental en algèbre qui dépasse largement le cadre du Taquin - on le retrouve en physique quantique, en topologie, en théorie des déterminants.
Le groupe alterné An est le sous-groupe de Sn formé par toutes les permutations paires. Il contient exactement n!/2 éléments - la moitié du groupe symétrique. Et c’est précisément ce sous-groupe qui décrit les configurations accessibles du Taquin.
Pourquoi le Taquin ne peut atteindre que An
L’explication tient à la nature des mouvements du puzzle. Quand vous glissez une pièce dans la case vide, vous effectuez une transposition entre cette pièce et la case vide. C’est une permutation impaire (une seule transposition).
Mais pour que la configuration finale soit une vraie « permutation des pièces », la case vide doit revenir à sa position de départ. Pour cela, elle doit effectuer un nombre pair de déplacements (autant de pas vers la droite que vers la gauche, autant vers le haut que vers le bas). Chaque déplacement étant une transposition impaire, un nombre pair de déplacements produit une permutation paire.
Résultat : depuis l’état résolu (qui est la permutation identité, une permutation paire), on ne peut atteindre que des permutations paires. Le Taquin est confiné dans le groupe alterné.
La signature comme critère de solubilité
La signature offre un outil pratique pour déterminer si une configuration est soluble. On calcule le nombre d’inversions : des paires de pièces (a, b) où a précède b dans la configuration mais a > b dans l’ordre naturel.
Pour un Taquin de côté impair (3×3, 5×5) :
- Nombre d’inversions pair = permutation paire = configuration soluble
- Nombre d’inversions impair = permutation impaire = configuration insoluble
Pour un Taquin de côté pair (4×4), la formule intègre aussi la position verticale de la case vide, car le retour de la case vide à sa position d’origine implique un nombre de transpositions qui dépend de la ligne.
Ce critère est nécessaire et suffisant. Il ne donne pas la solution, mais il garantit qu’une solution existe - ou qu’elle n’existera jamais.
Au-delà du Taquin : les groupes partout
La théorie des groupes ne se limite pas aux puzzles. Elle structure une part immense des mathématiques et de la physique :
- Le Rubik’s Cube forme un groupe de 43 milliards de milliards d’éléments, sous-groupe du groupe symétrique des facettes
- Les symétries cristallines en chimie sont décrites par 230 groupes d’espace
- Le modèle standard de la physique des particules repose sur les groupes de jauge SU(3) × SU(2) × U(1)
Le Taquin est ainsi une porte d’entrée concrète vers l’une des théories les plus puissantes des mathématiques. Manipuler des pièces sur une grille, c’est - littéralement - explorer la structure d’un groupe algébrique. Le Sudoku partage cette parenté mathématique : ses grilles valides sont gouvernées par des contraintes combinatoires qui, elles aussi, relèvent de l’algèbre abstraite.
La prochaine fois que vous glissez une pièce sur le Taquin, rappelez-vous que votre geste est une transposition dans un groupe symétrique, que la configuration sous vos yeux a une signature mathématique précise, et que l’impossibilité de certaines positions n’est pas un défaut du puzzle - c’est un théorème.