La Tour de Hanoï, présentation et règles du jeu.

La Tour de Hanoï est un grand classique dans l'univers des casse-têtes. Vous en avez certainement déjà croisé une ! Malgré les différentes variantes et formes existantes, le but reste le même : déplacer la Tour en un minimum de coups d'un point A à un point B. Mais pas si simple !

Tour de Hanoi 7 pièces casse-tête en bois

ORIGINE

La Tour de Hanoï est un puzzle, ou jeu mathématique, inventée en 1883 par Édouard Lucas, arithméticien français né à Amiens, professeur à Saint-Louis, et connu notamment pour ses travaux sur la théorie des nombres et ses Récréations mathématiques. Il prouvera d'ailleurs sa passion pour les jeux mathématiques et de réflexion en commercialisant son casse-tête sous le nom de N. Claus de Siam, professeur au collège de Li-Sou-Stian et prétendument son ami. Mais pour les plus perspicaces d'entre vous, vous aurez compris que ce pseudonyme est en réalité l'anagramme de son nom ( Lucas d'Amiens ) et de la ville où il enseignait ( Saint-Louis ).

La tour de Hanoï
Les Tours de Hanoï
Les Tours de Hanoï

LA LÉGENDE

Les Tours de Hanoï sont également connues sous le nom de Tours de Lucas ( vous savez maintenant pourquoi ! ), ou Tours de Brahma.
Brahma était le dieu créateur-démiurge de l'hindouisme, le premier membre de la Trimūrti, la trinité des déités hindoues majeures. Les autres membres sont Vishnou et Shiva.

La légende se passe au cœur du temple Kashi Vishwanath. Elle raconte que Brahma, au commencement des siècles, apporta dans ce temple, sous le dôme doré au centre du monde, 3 aiguilles de diamant, plantées dans une dalle de bronze, et 64 disques d'or pur, le plus large reposant sur l’airain, et les autres, de plus en plus étroits, superposés jusqu’au sommet. C'est la Tour sacrée de Brahma.

Les règles de Brahma sont simples : les prêtres doivent déplacer la tour de la première à la troisième aiguille, en ne déplaçant qu'un disque à la fois. Le disque déplacé doit l'être sur l'une des 2 autres aiguilles, et ne doit jamais être placé au-dessus d’un disque plus petit que lui. Nuit et jour, les prêtres se succèdent sur les marches de l’autel, occupés à transporter la Tour de la première aiguille sur la troisième. Lorsque les prêtres auront terminé, la tour et le temple tomberont, et ce sera la fin des mondes !

Si nous étudions les algorithmes de résolution de la Tour, le nombre de mouvements nécessaires pour déplacer les 64 disques de la première à la troisième colonne est de 18.446.744.073.551.615. Si on considère que les prêtres mettent 1 seconde pour déplacer 1 disque, il faudra plus de 5 milliards de siècles ( 5.845.580.504 exactement ! ) pour terminer la Tour. La fin du monde est encore loin !

A travers cette légende, certains pensent que Lucas fait ici encore parler sa passion pour les jeux et la réflexion.

Pas d'anagramme cette fois, mais des similitudes troublantes entre le nom du temple « Kashi Vishwanath » et le nom de l'ex champion du monde d'échec indien Viswanathan Anand. Et que dire de sa version géante de la Tour de Hanoï avec ses 64 disques … 64 … qui correspond au nombre de cases d'un échiquier …

RÈGLE DU JEU

Le départ

On dispose de 3 piquets fixés sur un socle, et d'un nombre n de disques de diamètres différents. Les disques sont empilés sur un piquet, en commençant du plus large au plus petit.
Le nombre de disques peut varier. Plus il y a de disques au départ, plus le jeu est difficile.

Le but

Déplacer les disques d'une tour de 'départ' à une tour 'd'arrivée' en passant par une tour 'intermédiaire', et ceci en un minimum de coups.

Comment

2 règles simples :

- on ne déplace qu’un seul disque à la fois, et le disque déplacé doit l'être sur l’un des deux autres piquets au choix ; c’est ce que l’on appelle un déplacement.

- le disque déplacé ne doit jamais être placé au-dessus d’un disque plus petit que lui.

RÉSOLUTION

La solution générale est donnée par l'algorithme suivant.

Algorithme récursif

La solution de base du jeu de la Tour de Hanoï est formulée de manière récursive.
Étiquetez les piquets avec A - B - C et numérotez les disques de 1 (le plus petit) à n (le plus grand). L'algorithme est exprimé comme suit:

1. Déplacez les n-1 premiers disques de A à B. (Cela laisse le disque n seul sur le piquet A)
2. Déplacez le disque n de A à C
3. Déplacez les n-1 disques de B à C

Pour déplacer n disques, il faut effectuer une opération élémentaire (déplacement d'un seul disque) et une opération complexe, c'est-à-dire le mouvement de n-1 disques. Cependant, cette opération se résout également de la même manière, en demandant comme opération complexe le déplacement de n-2 disques. En itérant ce raisonnement on réduit le processus complexe à un processus élémentaire, c’est-à-dire le déplacement de n-(n-1)=1 disque.
C'est un algorithme récursif de complexité exponentielle.

Il est intéressant de noter que le casse-tête peut être résolu pour n'importe quel "n", avec une démonstration par récurrence: supposons que nous ayons une tour en A composée de N disques, et supposons que N soit le nombre de disques maximum autorisés à résoudre le jeu. Au terme du déplacement de la tour de A à B, nous ajoutons à A un disque supplémentaire, de taille égale à N+1, et supposons que ce disque ait été arrêt tout le temps sous les autres. À ce stade, nous déplaçons simplement le disque de A à C, et nous pourrons certainement déplacer la tour de B à C en suivant les mêmes étapes que celles qui étaient nécessaires pour le faire de A à B. Après avoir montré qu’une tour de N disques peut être déplacée d’une colonne à une autre, il est également montré qu’on peut déplacer une tour de N+1 disques.

Aspects psychologiques

Ce casse-tête est utilisé en particulier dans la recherche psychologique, à travers la résolution des problèmes. Il est également utilisé comme test neuropsychologique.

Ce test peut détecter les mauvais fonctionnements des zones frontale et préfrontale et permet d’évaluer les fonctions exécutives telles que la planification, le travail, la mémoire et l’inhibition.
La résolution du jeu de la Tour de Hanoï dépend de l'activité inhibitrice, de la "mémoire de travail", c'est-à-dire l'utilisation de la mémoire à court terme, de la mémoire procédurale et de l'intelligence fluide. Ce test est similaire à celui de la Tour de Londres, ainsi qu'à celui des Tours de Toronto, utilisé avant tout pour évaluer les compétences de décision stratégique et résolution de problèmes chez avec les enfants de 4 à 13 ans et pour étudier les effets du vieillissement sur la résolution des problèmes simples.

Le casse-tête de la Tour de Hanoï est très joué en ligne, on peut trouver nombreuses réalisations pour ce jeu, en Flash et en Java.

Solution tour de Hanoï
Solution Tour de Hanoï

Commentaires (0)

Aucun commentaire pour l'instant

Nouveau commentaire

Pour vous apporter un meilleur service nous utilisons des cookies. En poursuivant votre navigation , vous acceptez l'utilisation de cookies.