jeu de taquin

Imaginez quinze carreaux serrés dans une boîte de seize cases. La seule place libre sert de passage : un carreau voisin y glisse, puis libère à son tour une case. Il est donc impossible de soulever une pièce ou de la faire passer en diagonale.

Ces déplacements paraissent très souples, mais ils conservent une information de parité. C'est elle qui sépare les mélanges que l'on peut ramener à l'ordre des mélanges bloqués, même après une longue suite de coups.

Un jeu de taquin de taille n×n contient n²−1 carreaux distincts et une unique case vide. Un coup fait glisser dans cette case un carreau qui lui est adjacent horizontalement ou verticalement. Une configuration décrit donc à la fois l'ordre des carreaux et la position du vide. La cible usuelle range les numéros dans l'ordre croissant, avec le vide en dernière case. Résoudre le puzzle consiste à atteindre cette cible ; chercher une solution minimale ajoute l'objectif de réduire le nombre de coups.

Pour tester la solubilité, on lit les carreaux ligne par ligne et l'on compte les inversions : une inversion est une paire dont le plus grand numéro apparaît avant le plus petit. On note I ce nombre. Si n est impair, la cible usuelle est atteignable exactement lorsque I est pair. Si n est pair, on note r le rang de la ligne vide en comptant depuis le bas, la dernière ligne ayant le rang 1. Le critère devient :

Cette convention vaut pour la cible usuelle. Pour comparer deux cibles quelconques, il faut comparer leurs invariants complets. Ce phénomène de parité s'interprète par les permutations produites par les coups autorisés.

Données. La grille est un taquin 4×4. La cible place 1 à 15 dans l'ordre, puis la case vide. La configuration étudiée place 1 à 14 dans l'ordre, puis le vide et enfin 15. La représentation des deux états rend visible le seul glissement nécessaire.

1. En lisant les carreaux ligne par ligne sans le vide, on obtient la suite 1, 2, …, 15.
2. Aucun grand numéro ne précède un plus petit : le nombre d'inversions est donc I = 0.
3. Le vide est sur la dernière ligne ; son rang depuis le bas est r = 1.
4. La somme vaut I + r = 1, qui est impaire : le critère du 4×4 annonce une configuration soluble.
5. Le carreau 15 glisse vers la gauche dans le vide. La cible est atteinte en un coup.
Contrôle. Aucun résultat positif inférieur à un coup n'est possible puisque les deux configurations diffèrent ; la solution est donc minimale.

Avant de chercher une suite de coups, le test de parité évite de travailler sur une position impossible. Sur une grille de largeur impaire, le nombre d'inversions suffit ; sur une largeur paire, il faut aussi relever la ligne du vide depuis le bas.

Pour vérifier un mélange, on écrit d'abord les numéros dans l'ordre de lecture en omettant le vide. On compte ensuite les paires inversées, puis on applique le critère adapté à la largeur de la grille.

Une fois la position déclarée soluble, la parité ne donne pas le chemin ni sa longueur. Il faut alors construire une suite de glissements ; si l'on cherche le minimum, on compare les solutions possibles par leur nombre de coups.

Configuration soluble et permutation paire. Sur une grille de largeur impaire, une position soluble par rapport à la cible usuelle a un nombre pair d'inversions. Sur un 4×4, ce raccourci est faux : une position avec un nombre impair d'inversions peut être soluble si le vide occupe une ligne de rang pair depuis le bas. Le critère testable porte alors sur I + r, pas sur I seul.

Largeur paire. Dire seulement « un nombre pair d'inversions » ne suffit pas pour le taquin classique 4×4. Le symptôme est une conclusion qui change quand le vide monte d'une ligne. Il faut combiner la parité de I avec le rang r de la ligne vide depuis le bas.

Case vide oubliée. Le vide n'entre pas dans la liste servant à compter I, mais sa position reste indispensable lorsque n est pair. Il faut donc l'omettre du décompte des inversions sans l'effacer de la configuration.

Cible différente. Les formules données supposent la cible usuelle, vide en dernière case. Si une autre cible est choisie, appliquer mécaniquement le même verdict peut être faux ; il faut comparer l'invariant de la position initiale à celui de cette cible.

Soluble ne signifie pas optimal. Le test établit l'existence d'une suite de coups, non sa longueur minimale. Après un verdict positif, une recherche de chemin reste nécessaire pour savoir combien de mouvements suffisent.

La parité découpe l'ensemble des configurations en classes que les glissements ne peuvent pas relier librement. Cette lecture ouvre sur la théorie des groupes : chaque coup modifie une permutation, tandis qu'un invariant détermine les états accessibles.

Permutation paire — Pour approfondir le lien entre nombre d'inversions, parité d'une permutation et configurations accessibles.