Taquin

Un article de Wikipédia, l'encyclopédie libre.

Taquin résolu

Le taquin est un jeu solitaire en forme de damier créé vers 1870 par l'Américain Sam Loyd. Il est composé de 15 petits carreaux numérotés de 1 à 15 qui glissent dans un cadre prévu pour 16.

Sommaire

1 Méthode générale de résolution
2 Anecdote
3 Voir aussi
- 3.1 Articles connexes
- 3.2 Liens externes

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 Cube de Rubik est aujourd'hui considéré comme l'un des « descendants » du taquin.

En ce qui concerne le taquin rectangulaire, rien ne permet d'affirmer qu'il offre ou non une solution possible : il faut essayer d'en trouver une pour connaître éventuellement la réponse.

[modifier] 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.

[modifier] Anecdote

Loyd affirma qu'il avait « affolé le monde entier » avec un taquin trafiqué. En effet, le problème posé était insoluble. Lorsque le jeu était vendu, l'espace vide était placé en bas à droite, et il fallait ordonner les nombres de 1 à 15, cet espace vide se retrouvant au même endroit. 1 000 USD étaient promis au gagnant, mais la récompense ne fut jamais réclamée.

Pour résoudre le taquin trafiqué, il aurait fallu échanger les places des carreaux 14 et 15. Or, les glissements ne permettent qu'un nombre pair d'échanges entre chiffres et cases vides. II existe plus de 600 milliards de dispositions possibles, et autant d'impossibles, dont celle proposée par Loyd. Il est toutefois possible d'ordonner les chiffres de 1 à 15 si la case vide est en haut à gauche. Bien qu'il soit possible de dire à l'avance si le problème posé est soluble ou non, il faut une certaine habileté pour l'effectuer concrètement en un moindre nombre de mouvements.