Jeu de taquin

Le taquin est un jeu solitaire en forme de damier créé vers 1870^[1] aux États-Unis. Sa théorie mathématique a été publiée par l'American Journal of mathematics pure and applied^[2] en 1879. En 1891, son invention fut revendiquée par Sam Loyd^[3], au moment où le jeu connaissait un engouement considérable, tant aux États-Unis qu'en Europe. Il est composé de 15 petits carreaux numérotés de 1 à 15 qui glissent dans un cadre prévu pour 16. Il consiste à remettre dans l'ordre les 15 carreaux à partir d'une configuration initiale quelconque.

Sommaire 1 Méthode générale de résolution 2 Anecdote 3 Configurations solubles et insolubles 4 Voir aussi 4.1 Articles connexes 4.2 Bibliographie 4.3 Liens externes 5 Notes et références

Le principe a été étendu à toutes sortes d'autres jeux. La plupart sont à base de blocs rectangulaires plutôt que carrés, mais le but est toujours de disposer les blocs d'une façon déterminée par un nombre minimal de mouvements. Le Rubik's Cube est aujourd'hui considéré comme l'un des « descendants » du taquin.

Méthode générale de résolution

Dans l'hypothèse où la case vide se trouve en bas à droite :

• remettre le jeu dans l'ordre ligne par ligne en commençant par la ligne du haut ;
• quand il ne reste plus que deux lignes mélangées, les réordonner colonne par colonne en commençant par celle de gauche.

Cette méthode ne garantit pas qu'un nombre minimal de mouvements sera effectué, mais est simple à mémoriser et aboutit dans tous les cas où une solution est possible.

Anecdote

Loyd affirma qu'il avait « rendu le monde entier fou » avec un taquin modifié. Dans la configuration proposée, les carreaux 14 et 15 étaient inversés, l'espace vide étant placé en bas à droite. Loyd prétendait avoir promis 1 000 USD à celui qui remettrait les carreaux dans l'ordre, mais la récompense n'aurait jamais été réclamée.

La résolution de ce problème est impossible. D'une part, il faut en effet échanger les places des carreaux 14 et 15, et l'on peut montrer que cette opération nécessite un nombre impair de glissements. D'autre part, il faut que la case vide retrouve sa place initiale, opération qui, quant à elle, nécessite un nombre pair de glissements. Il est toutefois possible d'ordonner les chiffres de 1 à 15 si la case vide est initialement en haut à gauche.

Configurations solubles et insolubles

Parmi toutes les dispositions initiales, il existe 10 461 394 944 000 dispositions dont la résolution est possible (à savoir la moitié de la factorielle de 16), et autant d'impossibles, dont celle proposée par Loyd.

Il est possible de dire à l'avance si le problème posé est soluble ou non. En effet, la configuration initiale d'un taquin est une permutation de sa configuration finale. Cette permutation est dite paire si elle peut être obtenue par un nombre pair d'échanges successifs de deux cases, adjacentes ou non, vide ou non, appelés également transpositions. On montre que cette notion ne dépend pas du choix de la suite des échanges. Elle est impaire sinon. On associe également à la case vide une parité : la case vide est paire si l'on peut se rendre de la position initiale de la case vide à la position finale en un nombre pair de déplacements, impair sinon.

Le problème sera soluble si la parité de la permutation est identique à la parité de la case vide.

• Exemple 1 : le problème de Sam Loyd est impossible. La case vide occupant la même place dans la configuration initiale et dans la configuration finale souhaitée, elle est paire (il faut 0 déplacement pour aller d'une position à l'autre). Mais puisque la configuration initiale s'obtient à partir de la configuration finale par la seule transposition des cases 14 et 15, la permutation est impaire. La case vide étant paire et la permutation impaire, le problème est insoluble.

• Exemple 2 : supposons que la configuration initiale soit telle que la case vide est en haut à gauche, suivie des carreaux dans l'ordre 1, 2, 3, ..., 13, 15, 14, ce que nous noterons (V, 1, 2, ..., 13, 15, 14). La configuration finale attendue est (1, 2, ..., 13, 14, 15, V). La case vide est paire, car on peut se rendre de sa position initiale (en haut à gauche) à sa position finale (en bas à droite) en faisant trois déplacements vers la droite puis trois déplacements vers le bas. La permutation est également paire, car on peut passer de (V, 1, 2, ..., 13, 15, 14) à (1, 2, ..., 13, 14, 15, V) en échangeant 14 et 15, puis en échangeant successivement V avec les 15 nombres qui suivent, (soit 16 transpositions en tout). La parité de la case vide étant identique à la parité de la permutation, la résolution est possible.

• Exemple 3 : Dans le taquin mélangé ci-contre, la case vide occupe une position paire. Par ailleurs, la position donnée est (13, 2, 3, 12, 9, 11, 1, 10, V, 6, 4, 14, 15, 8, 7, 5). Les transpositions permettant de passer de cette position à la position finale sont au nombre de 11, par exemple :

(13, 2, 3, 12, 9, 11, 1, 10, 5, 6, 4, 14, 15, 8, 7, V)

(13, 2, 3, 12, 9, 11, 1, 10, 5, 6, 4, 14, 7, 8, 15, V)

(13, 2, 3, 12, 9, 11, 1, 10, 5, 6, 4, 8, 7, 14, 15, V)

(7, 2, 3, 12, 9, 11, 1, 10, 5, 6, 4, 8, 13, 14, 15, V)

(7, 2, 3, 8, 9, 11, 1, 10, 5, 6, 4, 12, 13, 14, 15, V)

(7, 2, 3, 8, 9, 4, 1, 10, 5, 6, 11, 12, 13, 14, 15, V)

(7, 2, 3, 8, 9, 4, 1, 6, 5, 10, 11, 12, 13, 14, 15, V)

(7, 2, 3, 8, 5, 4, 1, 6, 9, 10, 11, 12, 13, 14, 15, V)

(7, 2, 3, 6, 5, 4, 1, 8, 9, 10, 11, 12, 13, 14, 15, V)

(1, 2, 3, 6, 5, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, V)

(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, V)

Il s'agit donc d'une permutation impaire. Etant impaire alors que la case vide est paire, la résolution est impossible.

L'algorithme proposé permet de déterminer si le problème posé est soluble ou non, mais ne donne pas la solution pour y parvenir. En particulier, il faut une certaine habileté pour l'effectuer concrètement en un moindre nombre de mouvements.

Voir aussi

Articles connexes

• L'Âne rouge
• Rubik's Cube

Bibliographie

• Edouard Lucas, Récréations mathématiques, 1891; réédition : Librairie Albert Blanchard, 1992, p. 187-218.

Liens externes

• (en) Version gratuite avec image en arrière-fond, pour Windows
• (en) Version gratuite pour Mac OS X
• (en) Article détaillant la parité du casse-tête
• (en) Applet Java pour résoudre le casse-tête
• (fr) Taquin gratuit sur Windows
• (fr) Un taquin sous gtk pour Linux et peut-être Windows et mac

Notes et références

• Portail des jeux