Le Taquin impossible : comment reconnaître une configuration insoluble
Vous avez certainement vécu cette expérience : après de longues minutes de manipulation acharnée, deux pièces du Taquin refusent obstinement de se placer correctement. Vous recommencez, vous essayez une autre approche, rien n’y fait. Et pour cause : la moitié de toutes les configurations possibles du Taquin sont mathématiquement impossibles à résoudre. Ce n’est pas une question de talent ou de patience : c’est une propriété fondamentale du puzzle, démontrée il y a près de 150 ans, qui plonge ses racines dans l’algèbre abstraite et la théorie des permutations.
L’arnaque de Sam Loyd et la découverte
L’histoire des Taquins insolubles commence en 1879, avec l’un des plus célèbres canulars mathématiques de l’histoire. Le puzzle-maker américain Sam Loyd créa un Taquin 4×4 (15 pièces) dont la configuration initiale était presque résolue : toutes les pièces étaient à leur place, sauf les numéros 14 et 15 qui étaient inversés. Loyd offrit une récompense de 1000 dollars à quiconque parviendrait à résoudre ce puzzle - une fortune pour l’époque.
Des milliers de personnes tentèrent leur chance. Personne ne réussit. Et pour cause : comme l’explique en détail notre article sur Sam Loyd et la célèbre arnaque mathématique, cette configuration est mathématiquement insoluble. Ce n’est pas Loyd qui l’a prouvé (il s’est contenté de l’exploiter), mais les mathématiciens Noyes Palmer Chapman et William Edward Story, qui démontrèrent en 1879 que certaines configurations du Taquin ne pouvaient pas être transformées en d’autres, quels que soient les mouvements effectués.
Cette découverte a posé les fondations mathématiques de ce qu’on appelle aujourd’hui la parité des permutations appliquée aux puzzles à glissement.
Comprendre les inversions
Pour saisir pourquoi certaines configurations sont insolubles, il faut d’abord comprendre la notion d’inversion. Dans un Taquin résolu, les pièces sont rangées dans l’ordre croissant : 1, 2, 3, 4, 5, 6, 7, 8 (pour un Taquin 3×3). On dit qu’il y a une inversion lorsqu’une pièce de valeur supérieure précède une pièce de valeur inférieure dans la séquence.
Prenons un exemple concret. Considérons la séquence 2, 1, 3, 4, 5, 6, 7, 8 (en lisant les pièces de gauche à droite, de haut en bas, en ignorant la case vide). Ici, le 2 précède le 1 : c’est une inversion. Le nombre total d’inversions est 1.
Autre exemple : la séquence 8, 7, 6, 5, 4, 3, 2, 1 - l’ordre complètement inversé. Chaque pièce précède toutes les pièces de valeur inférieure. Le nombre d’inversions est 8+7+6+5+4+3+2+1 = 28 inversions.
Le comptage des inversions est la clé pour déterminer la solubilité d’un Taquin. Voici comment procéder systématiquement :
- Listez toutes les pièces dans l’ordre de lecture (gauche à droite, haut en bas), en ignorant la case vide
- Pour chaque pièce, comptez combien de pièces de valeur inférieure apparaissent après elle dans la séquence
- Additionnez tous ces comptes : vous obtenez le nombre total d’inversions
Le théorème de solubilité
Le théorème qui régit la solubilité du Taquin s’énonce différemment selon la largeur de la grille (paire ou impaire).
Pour une grille de largeur impaire (3×3, 5×5, etc.) : une configuration est soluble si et seulement si le nombre d’inversions est pair. C’est la règle la plus simple. Si vous comptez un nombre impair d’inversions, le puzzle est impossible à résoudre, point final.
Pour une grille de largeur paire (4×4, 6×6, etc.) : la règle intègre également la position de la case vide. On compte la rangée de la case vide en partant du bas (rangée 1 = dernière ligne, rangée 2 = avant-dernière, etc.). Une configuration est soluble si et seulement si :
- La case vide est sur une rangée paire (en partant du bas) et le nombre d’inversions est impair
- OU la case vide est sur une rangée impaire (en partant du bas) et le nombre d’inversions est pair
En d’autres termes, pour les grilles de largeur paire, on additionne le nombre d’inversions et le numéro de rangée de la case vide (depuis le bas) : si cette somme est impaire, le puzzle est soluble.
La parité des permutations : l’explication profonde
Pourquoi cette règle fonctionne-t-elle ? La réponse se trouve dans l’algèbre des permutations, une branche des mathématiques qui étudie les réarrangements d’objets.
Chaque configuration du Taquin peut être décrite comme une permutation des pièces par rapport à la configuration résolue. Et chaque permutation a une parité : elle est soit paire, soit impaire, selon le nombre minimum de transpositions (échanges de deux éléments) nécessaires pour la décomposer. Un fait fondamental de l’algèbre est que la parité d’une permutation est unique : une permutation paire ne peut pas être décomposée en un nombre impair de transpositions, et vice versa.
Or, chaque mouvement du Taquin - glisser une pièce dans la case vide - équivaut à une transposition de la pièce avec la case vide. Chaque mouvement change donc la parité de la permutation. Comme notre article sur le Taquin et les mathématiques le détaille, cette contrainte de parité divise l’ensemble des configurations en deux classes étanches : les configurations paires et les configurations impaires. Aucune séquence de mouvements ne peut faire passer d’une classe à l’autre.
La configuration résolue appartient à la classe paire (zéro inversion = nombre pair). Donc, seules les configurations de même parité que la configuration résolue sont atteignables. Les autres sont à jamais hors de portée - c’est une impossibilité mathématique, pas une limitation pratique.
Vérifier la solubilité : un exemple pas à pas
Mettons la théorie en pratique avec un Taquin 3×3 concret. Supposons la configuration suivante (la case vide est représentée par un tiret) :
1 8 2 / - 4 3 / 7 6 5
Étape 1 : listez les pièces dans l’ordre de lecture, en ignorant la case vide : 1, 8, 2, 4, 3, 7, 6, 5.
Étape 2 : comptez les inversions pour chaque pièce :
- 1 : aucune pièce inférieure après → 0 inversions
- 8 : 2, 4, 3, 7, 6, 5 sont inférieurs → 6 inversions
- 2 : aucune pièce inférieure après → 0 inversions
- 4 : le 3 est inférieur → 1 inversion
- 3 : aucune pièce inférieure après → 0 inversions
- 7 : 6 et 5 sont inférieurs → 2 inversions
- 6 : le 5 est inférieur → 1 inversion
- 5 : aucune pièce inférieure après → 0 inversions
Étape 3 : total des inversions = 0 + 6 + 0 + 1 + 0 + 2 + 1 + 0 = 10.
Étape 4 : la grille est de largeur 3 (impaire), donc la règle est simple : 10 est pair, donc cette configuration est soluble.
Si le 1 et le 2 étaient inversés (séquence 2, 8, 1, 4, 3, 7, 6, 5), le total des inversions passerait à 11 (impair), et la configuration serait insoluble.
Les conséquences pratiques
Cette propriété mathématique a des implications directes pour la conception et la pratique du Taquin.
Pour les fabricants de puzzles. Tout Taquin physique vendu dans le commerce doit être assemblé dans une configuration soluble. Si les pièces sont simplement mélangées au hasard, il y a exactement une chance sur deux que le puzzle soit impossible. C’est pourquoi les Taquins sérieux sont mélangés à partir de la position résolue, par des mouvements légaux, plutôt que par un placement aléatoire des pièces.
Pour les programmeurs. Les générateurs de Taquin numériques doivent impérativement vérifier la solubilité avant de proposer un puzzle au joueur. Un générateur naïf qui placerait les pièces aléatoirement produirait des puzzles insolubles dans 50 % des cas - une source de frustration garantie. La vérification algorithmique par comptage des inversions est rapide (complexité O(n²)) et fiable.
Pour les joueurs. Si vous possédez un Taquin physique dont les pièces peuvent être retirées et replacées manuellement, méfiez-vous. Il suffit d’inverser deux pièces pour rendre le puzzle insoluble. Si quelqu’un vous remet un Taquin prétendument mélangé et que vous ne parvenez pas à le résoudre malgré tous vos efforts, vérifiez la parité avant de douter de vos compétences.
Au-delà du Taquin : un théorème universel
Le théorème de solubilité du Taquin n’est pas un résultat isolé. Il s’inscrit dans un cadre mathématique beaucoup plus vaste : la théorie des groupes. L’ensemble des configurations accessibles du Taquin forme un groupe de permutations, et les propriétés de ce groupe déterminent ce qui est possible et ce qui ne l’est pas.
On retrouve des contraintes similaires dans d’autres puzzles : le Rubik’s Cube, par exemple, possède ses propres règles de solubilité. Si vous démontez un Rubik’s Cube et remontez les pièces au hasard, il y a exactement une chance sur douze que la configuration soit soluble. Les contraintes sont différentes (parité des coins, parité des arêtes, orientation des pièces), mais le principe fondamental est le même : les mouvements légaux ne permettent d’atteindre qu’une fraction de toutes les configurations possibles.
Le Taquin impossible nous rappelle une vérité profonde : les mathématiques ne sont pas un obstacle à la résolution des puzzles - elles en sont la clé. Comprendre la parité des permutations, ce n’est pas seulement savoir quand un puzzle est insoluble. C’est comprendre la structure invisible qui gouverne chaque mouvement, chaque configuration, chaque chemin vers la solution. Et cette compréhension transforme le Taquin d’un simple jeu de patience en une porte d’entrée vers l’un des domaines les plus élégants des mathématiques.