Le casse-tête des disques, dans le navigateur
Cette tour de Hanoï en ligne se joue à la souris, au doigt ou au clavier. Une pile de disques de tailles différentes est posée sur la tige de gauche. Le but : la reconstruire, dans le même ordre, sur la tige de droite. Choisissez de 3 à 10 disques et jouez avec « 3 tiges », la version classique, ou « 4 tiges » pour une variante plus courte. « Coups » compte vos déplacements, « Minimum » rappelle l'objectif.
Les règles et les commandes
- On ne déplace qu'un disque à la fois : celui du dessus d'une tige.
- Un disque ne se pose jamais sur un disque plus petit. Un coup interdit est refusé et un message explique pourquoi.
- Faites glisser le disque du dessus vers une autre tige, ou touchez la tige de départ puis la tige d'arrivée.
- Au clavier, sélectionnez le plateau : les touches 1 à 4 désignent la tige de départ puis la tige d'arrivée. Flèches et Entrée marchent aussi, Échap annule.
La partie en cours reprend à la visite suivante. Le tableau « Meilleurs scores » garde, pour chaque nombre de disques et de tiges, les parties gagnées, le moins de coups et le meilleur temps.
Combien de coups faut-il ?
Avec 3 tiges, le minimum vaut 2 multiplié par lui-même autant de fois qu'il y a de disques, moins 1, ce qu'on écrit 2^n − 1. Pour déplacer le plus grand disque, il faut d'abord ranger tous les autres sur la tige du milieu, puis le poser à droite, puis remettre les autres par-dessus. Chaque disque ajouté double donc le travail, plus un coup.
| Disques | 3 tiges | 4 tiges |
|---|---|---|
| 3 | 7 | 5 |
| 5 | 31 | 13 |
| 8 | 255 | 33 |
| 10 | 1 023 | 49 |
Avec 10 disques et un coup par seconde, une partie parfaite dure 17 minutes et 3 secondes. Dans une pile de 3 disques, le petit bouge 4 fois, le moyen 2 fois et le grand une seule fois : 4 + 2 + 1 = 7. Ces nombres sont les puissances de 2, et c'est aussi en binaire qu'on lit le mieux la partie : au coup numéro 4, qui s'écrit 100 avec le convertisseur binaire, c'est le disque 3 qui bouge, car l'écriture finit par deux zéros.
La stratégie gagnante
- Le petit disque bouge un coup sur deux, toujours dans le même sens de rotation. Avec un nombre impair de disques, il part d'abord vers la tige de droite ; avec un nombre pair, vers celle du milieu.
- Entre deux coups du petit disque, un seul autre déplacement est permis : faites-le.
Avec 4 tiges, la méthode habituelle met quelques petits disques de côté sur une tige libre, déplace les autres comme avec 3 tiges, puis replace les premiers. Personne n'a encore démontré qu'on ne peut pas faire mieux dans tous les cas : le minimum affiché est donc marqué « conjecturé ». Pour un autre casse-tête où il faut prévoir plusieurs coups à l'avance, essayez le jeu du taquin ou le solitaire à billes.
La solution animée
« Montrer la solution » joue les coups un par un, à la vitesse choisie dans « Vitesse de la solution ». Au départ, elle prend exactement le minimum de coups. En cours de partie à 3 tiges, elle repart de votre position par le chemin le plus court ; à 4 tiges, elle recommence la partie. « Pause » et « Coup suivant » permettent de suivre pas à pas. Si votre appareil demande moins d'animations, chaque coup attend un clic sur « Coup suivant ». Une partie aidée ne compte pas dans les records.
Un peu d'histoire
Le jeu est vendu en France à la fin du XIXe siècle, en 1883 selon la plupart des sources, avec la légende d'un temple où des moines déplaceraient 64 disques d'or. Cette légende semble avoir été écrite pour accompagner le jouet, et rien ne montre un lien réel avec la ville de Hanoï.
Questions fréquentes
Combien de temps durerait la légende des 64 disques ?
Il faudrait 18 446 744 073 709 551 615 coups. À un coup par seconde, cela fait environ 585 milliards d'années.
Peut-on finir sur la tige du milieu ?
Non, l'outil attend toute la pile sur la tige de droite. Par symétrie, le nombre minimal de coups serait exactement le même.
Par combien de disques commencer avec un enfant ?
Avec 3 disques, 7 coups suffisent : c'est idéal pour découvrir la règle. Passez à 4 ou 5 ensuite.
Pourquoi le chronomètre ne tourne-t-il pas ?
Il démarre au premier coup et s'arrête quand la tour est montée. Après un rechargement, il reprend au coup suivant.