Comment jouer aux tours de Hanoï ?
Trois piquets, et sur celui de gauche une tour de disques, du plus grand en bas au plus petit en haut. Il faut reconstruire la tour sur le piquet de droite en respectant deux règles :
- on ne déplace qu'un disque à la fois, celui du haut d'un piquet ;
- on ne pose jamais un disque sur un disque plus petit.
Touchez un piquet pour soulever son disque du haut, puis touchez le piquet où le poser, ou faites glisser le disque de l'un à l'autre. Au clavier, tapez 1, 2 ou 3. Le chronomètre part au premier coup.
Le nombre minimum de coups
Pour déplacer une tour de n disques, il faut d'abord déplacer les n − 1 disques du dessus, puis le plus grand, puis à nouveau les n − 1 autres par-dessus. Chaque disque en plus double donc le travail, plus un coup : le minimum vaut 2 puissance n, moins 1.
| Disques | Coups au minimum |
|---|---|
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
Une méthode pour finir
Un coup sur deux, déplacez le plus petit disque, toujours dans le même sens de rotation. Avec un nombre impair de disques, il va de gauche à droite, puis au milieu, puis à gauche ; avec un nombre pair, de gauche au milieu, puis à droite, puis à gauche.
L'autre coup ne laisse jamais le choix : le plus petit disque mis à part, un seul déplacement est permis entre les deux autres piquets. Jouez-le, puis revenez au petit disque.
Un peu d'histoire
Le problème a été inventé par le mathématicien français Édouard Lucas. Il paraît d'abord en fascicule en 1889, puis dans le troisième tome de ses Récréations mathématiques, publié en 1892 après sa mort. Lucas l'attribue à un ami, N. Claus de Siam : l'anagramme de « Lucas d'Amiens ».
La légende qui l'accompagne parle du grand temple de Bénarès : trois aiguilles de diamant, et 64 disques d'or que des prêtres déplacent nuit et jour selon ces règles. Quand la tour sera reconstruite, ce sera la fin du monde. À raison d'une seconde par disque, les 264 − 1 coups demanderaient environ 584,5 milliards d'années.
Questions fréquentes
Combien de coups faut-il au minimum ?
2 puissance n, moins 1, pour n disques : 7 coups avec 3 disques, 15 avec 4, 31 avec 5, jusqu'à 255 avec 8. Le minimum est affiché au-dessus du plateau.
Comment déplacer un disque au doigt ?
Touchez le piquet de départ : son disque du haut se soulève. Touchez ensuite le piquet d'arrivée. Vous pouvez aussi faire glisser le disque d'un piquet à l'autre.
Peut-on jouer au clavier ?
Oui. Tapez 1, 2 ou 3 pour prendre le disque du haut d'un piquet, puis le numéro du piquet où le poser. Les flèches gauche et droite passent d'un piquet à l'autre, Entrée prend ou pose, Échap repose le disque.
Que fait le bouton Solution ?
Il joue lui-même les coups qui restent, par le chemin le plus court depuis la position où vous êtes. La partie n'entre alors pas dans vos records.
Mes records sont-ils enregistrés ?
Oui, dans votre navigateur seulement : le moins de coups, puis le meilleur temps, pour chaque nombre de disques. Rien n'est envoyé à Lycos.
Un problème dans le jeu ? Signalez-le, nous le corrigeons.