Le Taquin et les mathématiques
12 mars 2026
Derrière l'apparente simplicité du Taquin se cache un univers mathématique d'une richesse surprenante. Ce puzzle coulissant a fasciné les mathématiciens depuis le XIXe siècle et continue de servir de terrain d'étude en théorie des groupes, en combinatoire et en intelligence artificielle. Plongeons dans les mathématiques qui gouvernent ce casse-tête légendaire.
Permutations et états du puzzle
Un Taquin 4×4 est composé de 15 tuiles numérotées et d'une case vide, disposées dans une grille de 16 cases. Le nombre total de configurations possibles est de 16! / 16 = 15!, soit exactement 1 307 674 368 000 (plus de 1 300 milliards) d'arrangements différents. C'est un nombre colossal qui rend l'exploration exhaustive par un humain absolument impossible.
Chaque configuration du Taquin peut être représentée comme une permutation, c'est-à-dire un réarrangement des nombres de 1 à 15 (plus la case vide). La théorie des permutations, une branche de l'algèbre, fournit les outils nécessaires pour analyser les propriétés fondamentales du puzzle.
La parité des inversions : pourquoi certains Taquins sont impossibles
La découverte mathématique la plus célèbre liée au Taquin concerne sa résolvabilité. Sur les 1 300 milliards de configurations possibles, exactement la moitié - soit environ 650 milliards - sont résolubles. L'autre moitié est mathématiquement impossible à résoudre, peu importe le nombre de mouvements effectués.
Pour déterminer si une configuration est résoluble, on utilise le concept d'inversion. Une inversion se produit lorsqu'une tuile de valeur supérieure précède une tuile de valeur inférieure dans la séquence (en lisant la grille de gauche à droite, de haut en bas, en ignorant la case vide). Par exemple, si la tuile 5 apparaît avant la tuile 3, c'est une inversion.
La règle est la suivante pour un Taquin de largeur paire (comme le 4×4) : une configuration est résoluble si et seulement si la parité du nombre d'inversions et la parité de la rangée de la case vide (comptée depuis le bas) sont de même parité. Pour un Taquin de largeur impaire (comme le 3×3), c'est plus simple : la configuration est résoluble si le nombre d'inversions est pair.
C'est précisément ce théorème qui rendait le célèbre défi de Sam Loyd impossible. En inversant uniquement les pièces 14 et 15 par rapport à la solution, on change la parité des inversions d'exactement 1, rendant la configuration insoluble. Les mathématiciens Johnson et Story ont prouvé ce résultat dès 1879, mettant fin au débat.
Théorie des groupes et structure algébrique
Les déplacements possibles dans le Taquin forment un groupe au sens algébrique du terme. Plus précisément, l'ensemble des configurations accessibles depuis l'état résolu forme un sous-groupe du groupe symétrique S15. Ce sous-groupe est isomorphe au groupe alterné A15, le groupe des permutations paires de 15 éléments.
Cette structure de groupe explique pourquoi exactement la moitié des configurations sont accessibles : le groupe alterné An a toujours un indice 2 dans le groupe symétrique Sn. Les mouvements du Taquin ne peuvent produire que des permutations paires, ce qui exclut définitivement la moitié des arrangements.
Complexité de l'espace d'états
La résolution optimale du Taquin - trouver la solution avec le minimum de mouvements - est un problème algorithmiquement difficile. Il a été démontré que le problème généralisé du Taquin (pour une grille n×n) est NP-difficile, ce qui signifie qu'il n'existe probablement pas d'algorithme efficace pour trouver la solution optimale dans tous les cas.
Pour le Taquin 4×4 standard, le nombre maximal de mouvements nécessaires pour résoudre n'importe quelle configuration est de 80. Ce nombre, appelé le « diamètre » du graphe d'états, a été déterminé par calcul informatique. La distance moyenne est d'environ 53 mouvements.
Pour le Taquin 3×3, plus petit, le diamètre est de 31 mouvements et la distance moyenne est d'environ 22. L'espace d'états est suffisamment petit (181 440 configurations accessibles) pour être entièrement exploré par un ordinateur.
Le Taquin en intelligence artificielle
Le Taquin est devenu un problème de référence en intelligence artificielle, particulièrement pour tester les algorithmes de recherche. L'algorithme A*, inventé par Hart, Nilsson et Raphael en 1968, utilise souvent le Taquin comme illustration. Cet algorithme combine la recherche en largeur avec une fonction heuristique pour trouver le chemin optimal.
Les heuristiques les plus courantes pour le Taquin sont la distance de Manhattan (somme des distances de chaque tuile à sa position cible) et les bases de données de motifs (pattern databases), qui précalculent les distances exactes pour des sous-ensembles de tuiles. Avec ces heuristiques avancées, même les configurations les plus difficiles du Taquin 4×4 peuvent être résolues de manière optimale en quelques secondes.
Ainsi, derrière chaque glissement de tuile se cache un monde de structures mathématiques élégantes. Le Taquin illustre parfaitement comment un objet simple peut engendrer des questions profondes, à la frontière entre les mathématiques pures et l'informatique.