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.
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, etc., 13, 15, 14, ce que nous noterons (V, 1, 2, etc., 13, 15, 14). La configuration finale attendue est (1, 2, etc., 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, etc., 13, 15, 14) à (1, 2, etc., 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. Étant 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.
Algorithmique
Le problème algorithmique de savoir si une configuration d'un taquin est gagnante est facile (dans la classe P), mais le problème de trouver le plus court chemin pour arriver à la configuration gagnante est NP-difficile[4] - [5].
Exemples de jeu de Taquin
Divers jeux en ligne sont inspirés du mécanisme du jeu de taquin. Par exemple les jeux
Notes et références
- Jerry Slocum & Dic Sonneveld, The 15 Puzzle, (ISBN 1-890980-15-3)
- cité par Edouard Lucas, dans Récréations mathématiques (1891), réédition Librairie Blanchard (1992), p. 190
- Le taquin apparaît p. 235 dans Sam Loyd's Cyclopedia of 5000 Puzzles, Tricks, and Conundrums. Version française : Martin Gardner, Les casse-tête mathématiques de Sam Loyd, Bordas (1970), p. 17, (ISBN 2-04-010348-1)
- Daniel Ratner, Manfred K. Warmuth. Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable. National Conference on Artificial Intelligence, 1986.
- Daniel Ratner et Warmuth, Manfred, « The (n2−1)-puzzle and related relocation problems », Journal of Symbolic Computation, vol. 10, no 2, , p. 111–137 (DOI 10.1016/S0747-7171(08)80001-6)
- Interview du développeur du jeu : http://jeuxgratuitsenligne.over-blog.com/-continuity-uses-an-analogy-to-the-n-puzzle
- Interview de Kim Jongwa, développeur du jeu : http://jeuxgratuitsenligne.over-blog.com/kim-jonghwa-that-night-i-came-up-with-the-mechanic-of-rooms
Voir aussi
Bibliographie
- Édouard Lucas, Récréations mathématiques, 1891; réédition : Librairie Albert Blanchard, 1992, p. 187-218.