Jeu de taquin

Jeu de taquin

Taquin

Taquin résolu

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

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

Position initiale du taquin de Sam Loyd

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

Article détaillé : Groupe alterné.

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.
Variante résoluble du taquin de Loyd
  • 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.
Taquin mélangé
  • 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

Bibliographie

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

Liens externes

Notes et références

  1. Jerry Slocum & Dic Sonneveld, The 15 Puzzle, ISBN 1-890980-15-3
  2. cité par Edouard Lucas, dans Récréations mathématiques (1891), réédition Librairie Blanchard (1992), p.190
  3. 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
  • Portail des jeux Portail des jeux

Ce document provient de « Taquin ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Jeu de taquin de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Jeu de taquin — 15 Puzzle     …   Deutsch Wikipedia

  • Jeu de taquin — In the mathematical field of combinatorics, jeu de taquin is a construction due to Schützenberger [Schützenberger 1977] which defines an equivalence relation on the set of skew standard Young tableaux. A jeu de taquin slide is a transformation… …   Wikipedia

  • Taquin — résolu 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 …   Wikipédia en Français

  • Jeu de pousse-pousse — Le jeu de pousse pousse est constitué par un rectangle en plastique dans lequel se trouvent des lettres de l alphabet pouvant glisser les unes sur les autres. Une des cases est vide. le jeu vise à former un mot dans la ligne du haut. Une variante …   Wikipédia en Français

  • taquin — taquin, ine [ takɛ̃, in ] adj. • 1442 « homme violent, querelleur »; tacain « gueux » 1411; de l a. fr. taquehan « émeute » (1244), du moy. néerl. takehan ♦ Qui prend plaisir à taquiner autrui. Un enfant taquin. « Elle me faisait faire des… …   Encyclopédie Universelle

  • Fort Boyard (jeu télévisé) — Pour les articles homonymes, voir Fort Boyard (homonymie). Fort Boyard Logo du jeu télévisé Fort Boyard depuis 2009 …   Wikipédia en Français

  • Fort Boyard (Jeu Télévisé) — Pour les articles homonymes, voir Fort Boyard (homonymie). Fort Boyard Logo du jeu télévisé Fort Boyard en 2009 …   Wikipédia en Français

  • Fort Boyard (jeu televise) — Fort Boyard (jeu télévisé) Pour les articles homonymes, voir Fort Boyard (homonymie). Fort Boyard Logo du jeu télévisé Fort Boyard en 2009 …   Wikipédia en Français

  • Fort boyard (jeu télévisé) — Pour les articles homonymes, voir Fort Boyard (homonymie). Fort Boyard Logo du jeu télévisé Fort Boyard en 2009 …   Wikipédia en Français

  • Groupe Alterné — En mathématiques, et plus précisément en théorie des groupes, le groupe alterné de degré n, souvent noté An, est un sous groupe distingué du groupe symétrique des permutations d un ensemble fini de cardinal n. Ce sous groupe est composé des… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”