Taquin insoluble ? La règle de parité pour savoir si une grille a une solution

Par Dawid Siedlarz · · 7 min de lecture

Jouer à Taquin gratuitement →

En bref : non, toutes les grilles de taquin n'ont pas de solution. Exactement la moitié des dispositions peut être résolue, l'autre moitié jamais. Pour vérifier une grille, comptez les inversions (paires de pièces dans le mauvais ordre) : sur un taquin 3 × 3 ou 5 × 5, il est soluble si ce nombre est pair ; sur le taquin 4 × 4 (le jeu du 15), si les inversions plus la ligne de la case vide comptée depuis le bas donnent un nombre impair. William Johnson et William Story l'ont démontré en 1879, et c'est pourquoi personne n'a jamais gagné le prix de Sam Loyd pour remettre le 14 et le 15 dans l'ordre. Notre Taquin ne propose que des grilles solubles.

Try it right here, or open Sliding Puzzle full screen.

Si vous vous êtes déjà acharné une heure sur un taquin en plastique pour finir avec les deux dernières pièces inversées, ce n'était sans doute pas votre faute. Quelqu'un a sorti les pièces et les a remises dans un autre ordre, et cela rend le taquin impossible une fois sur deux. Voici comment le savoir en une minute, et pourquoi la règle fonctionne.

Combien de positions du taquin ont une solution ?

On compte toutes les façons de placer les pièces et la case vide, puis on divise par deux. Nous avons vérifié cette moitié par la force brute sur le taquin 3 × 3 : une recherche depuis la position résolue atteint exactement 181 440 des 362 880 dispositions, et la règle ci-dessous désigne les mêmes 181 440, sans exception.

GrilleDispositionsSolublesPosition la plus difficile
3 × 3 (taquin à 8 pièces)362 880181 44031 coups (2 positions)
4 × 4 (jeu du 15)20 922 789 888 00010 461 394 944 00080 coups (17 positions)
5 × 5 (24 pièces)environ 1,55 × 1025environ 7,76 × 1024–

Un coup, ici, c'est une pièce qui glisse d'une case. En plaçant au hasard les 16 éléments d'une grille 4 × 4 20 000 fois, nous avons obtenu 50,3 % de grilles solubles, comme le prévoit la théorie.

Comment savoir si un taquin est soluble

  1. Écrivez les pièces dans l'ordre de lecture, de gauche à droite et de haut en bas, sans la case vide.
  2. Comptez les inversions. Pour chaque pièce, comptez combien de pièces plus petites viennent après elle dans la liste, puis additionnez.
  3. Grilles de largeur impaire (3 × 3, 5 × 5) : le taquin est soluble si le total est pair.
  4. Grilles de largeur paire (4 × 4) : ajoutez le numéro de la ligne où se trouve la case vide, la ligne du bas valant 1. Le taquin est soluble si ce total est impair.

Deux exemples sur le taquin 3 × 3, case vide en bas à droite :

  • 1 2 3 / 4 5 6 / 8 7 _ : seule la paire 8, 7 est dans le désordre, soit 1 inversion. C'est impair, donc impossible.
  • 8 6 7 / 2 5 4 / 3 _ 1 : 24 inversions. C'est pair, donc soluble. C'est même l'une des deux positions les plus difficiles du taquin 3 × 3 : la solution la plus courte demande 31 coups.

Et le « 14-15 » de Sam Loyd : les 15 pièces sont dans l'ordre sauf le 15 placé avant le 14, soit 1 inversion, et la case vide est sur la ligne du bas, ce qui ajoute 1. Le total vaut 2, un nombre pair : la position est impossible.

Pourquoi la règle marche : la preuve en trois étapes

  1. Chaque coup est un échange. Voyez la case vide comme une seizième pièce. Faire glisser une pièce dans le trou revient à échanger les deux. Toute position atteinte est donc la grille résolue à laquelle on a appliqué un certain nombre d'échanges.
  2. La case vide compte les échanges. Coloriez la grille comme un damier. À chaque coup, la case vide passe sur une case de l'autre couleur : elle ne peut revenir dans son coin qu'après un nombre pair de coups.
  3. La parité des échanges ne change jamais. Une même disposition peut s'obtenir par bien des suites d'échanges, mais elles sont toutes de longueur paire ou toutes de longueur impaire. C'est la signature d'une permutation, la même notion que dans le calcul d'un déterminant.

Conclusion : toute position avec la case vide dans son coin est à un nombre pair d'échanges du départ. Échanger seulement le 14 et le 15 est un seul échange, impair, donc hors d'atteinte. C'est la moitié de la preuve de 1879 qui exclut des positions ; le même article démontre aussi l'autre moitié : toute disposition du bon côté peut réellement être atteinte.

Le comptage des inversions est un raccourci pour la même idée. Sur un taquin 3 × 3, un coup horizontal ne change pas l'ordre de lecture, et un coup vertical fait sauter une pièce par-dessus 2 autres, ce qui change les inversions de 0 ou de 2 : leur parité ne bouge pas. Sur un 4 × 4, le saut passe par-dessus 3 pièces et inverse la parité, mais la case vide change aussi de ligne, si bien que inversions plus ligne de la case vide gardent la même parité. La grille résolue a 0 inversion et la case vide en ligne 1, soit un total de 1 : impair.

Le « 14-15 » et la folie de 1880

On attribue généralement le jeu à Noyes Palmer Chapman, receveur des postes à Canastota, dans l'État de New York. Le jeu est en vente dès décembre 1879, Chapman dépose une demande de brevet en février 1880 (refusée), et la même année le jeu devient une véritable folie aux États-Unis. La preuve arrive presque aussitôt : les « Notes on the '15' Puzzle » de Johnson et Story paraissent dans l'American Journal of Mathematics en 1879. En France, Édouard Lucas consacre un chapitre au « jeu du taquin » dans ses Récréations mathématiques.

De 1891 à sa mort en 1911, l'auteur de casse-tête Sam Loyd a prétendu avoir inventé le jeu, ce qui est faux, et il a parlé d'un prix de 1 000 dollars pour qui remettrait le 14 et le 15 dans l'ordre. L'argument de parité montre que personne ne le pouvait.

AnnéeÉvénement
1879Le jeu est en vente aux États-Unis ; Johnson et Story publient la preuve
1880Demande de brevet de Chapman (refusée) ; le jeu devient une folie
1891Sam Loyd commence à se dire l'inventeur du jeu
1986Ratner et Warmuth montrent que trouver la solution la plus courte sur une grille n × n est NP-difficile
1999Brüngger, Marzetta, Fukuda et Nievergelt prouvent que les positions les plus difficiles du jeu du 15 demandent 80 coups

Soluble ne veut pas dire facile à résoudre vite

Savoir si une grille a une solution prend une minute avec la règle ci-dessus. Trouver la solution la plus courte est un autre problème : pour le taquin n × n en général, il est NP-difficile, c'est-à-dire qu'on ne connaît pas de méthode rapide pour les grandes grilles. C'est pourquoi on résout le taquin avec une méthode fixe (la ligne du haut d'abord, puis la colonne de gauche, puis le petit taquin qui reste) plutôt qu'en cherchant le chemin optimal. La méthode décrite sur la page de notre Taquin marche à tous les coups, avec plus de coups que le minimum.

Que faire si votre taquin n'a pas de solution ?

  • Taquin en plastique ou en bois : sortez deux pièces quelconques et échangez-les. Un seul échange fait passer la grille dans l'autre moitié : un taquin impossible devient soluble (et inversement).
  • Taquin que vous programmez : ne placez pas les pièces au hasard. Partez de la grille résolue et faites glisser des pièces, ou mélangez au hasard et échangez deux pièces chaque fois que la règle dit que la grille est impossible.
  • Deux pièces inversées à la fin : avec tout le reste en place et la case vide dans son coin, cette position est du côté impossible, et aucun coup ne fait changer de côté. La grille était donc impossible dès le départ ; vous n'avez pas fait d'erreur.

La règle de parité dans notre Taquin

Notre Taquin a trois tailles : Facile en 3 × 3, Moyen en 4 × 4 (le jeu du 15 classique) et Difficile en 5 × 5. Il ne place jamais les pièces au hasard : il part de la grille résolue et déplace la case vide au hasard, 40 pas par case (360 en Facile, 640 en Moyen, 1 000 en Difficile), si bien que chaque grille est du côté soluble. Nous avons vérifié 60 000 de ses grilles avec la règle : toutes l'ont passée.

Le compteur de coups compte chaque pièce qui glisse, comme les chiffres ci-dessus, ce qui permet de se comparer au meilleur possible. Sur 20 000 de nos grilles Facile, la solution la plus courte faisait en moyenne 22,0 coups (médiane 22, maximum 30). Si vous aimez les casse-tête cachant une règle mathématique, les tours de Hanoï en ont une aussi (2n − 1 coups), et le Sokoban (en anglais) est le casse-tête de pousse-pousse où une seule mauvaise poussée peut rendre un niveau impossible.

Questions fréquentes

Toutes les grilles de taquin ont-elles une solution ?

Non. Sur les 20 922 789 888 000 façons de placer les 15 pièces et la case vide d'un taquin 4 x 4, exactement la moitié peut être résolue et l'autre jamais. Un taquin mélangé en faisant glisser les pièces a toujours une solution ; un taquin remonté à la main, pièces sorties puis remises, n'en a qu'une fois sur deux.

Comment savoir si un taquin est soluble ?

Lisez les pièces ligne par ligne sans la case vide et comptez les inversions, c'est-à-dire les paires où un grand nombre précède un plus petit. Sur une grille 3 x 3 ou 5 x 5, le taquin est soluble si ce nombre est pair. Sur une grille 4 x 4, ajoutez la ligne de la case vide comptée depuis le bas (ligne du bas = 1) : il est soluble si le total est impair.

Pourquoi ne peut-on pas échanger le 14 et le 15 ?

Chaque coup échange la case vide avec une pièce, et la case vide ne peut revenir dans son coin qu'après un nombre pair de coups. Toute position atteinte avec la case vide dans le coin est donc à un nombre pair d'échanges du départ. Échanger seulement le 14 et le 15, c'est un seul échange, un nombre impair : aucune suite de coups n'y mène.

Combien de coups faut-il au maximum pour résoudre un taquin ?

80 coups d'une pièce pour le taquin 4 x 4 : Brüngger, Marzetta, Fukuda et Nievergelt ont prouvé en 1999 que les positions les plus difficiles en demandent 80, et Richard Korf en a ensuite compté 17. Pour le taquin 3 x 3, le maximum est de 31 coups, et seules deux positions en demandent autant.

Qui a prouvé que la moitié des positions sont impossibles ?

William Woolsey Johnson et William Edward Story, dans « Notes on the '15' Puzzle », publié en 1879 dans l'American Journal of Mathematics. L'article démontre les deux moitiés du résultat : la moitié des positions est impossible, et toutes les autres peuvent être résolues.