Tours de Hanoï

Qu'est-ce que les Tours de Hanoï ?

Les Tours de Hanoï sont le casse-tête que le mathématicien français Édouard Lucas fit paraître à Paris en 1883, sous le nom inventé de « professeur N. Claus de Siam », anagramme de « Lucas d'Amiens ». Le jeu se présentait comme un socle en bois à trois tiges avec une tour de huit disques, accompagné d'une légende : dans un grand temple, des prêtres déplacent une tour de 64 disques d'or d'une aiguille de diamant à une autre, un disque à la fois, jamais un disque plus grand sur un plus petit, et quand ils auront fini, le monde prendra fin. Joué parfaitement, 64 disques demandent 2^64 - 1 coups, plus de 18 milliards de milliards : à un coup par seconde, environ 585 milliards d'années.

Les règles tiennent en une ligne : déplacez toute la tour sur la tige cible, un disque à la fois, sans jamais poser un disque plus grand sur un plus petit. Pour une tour de n disques sur trois tiges, le minimum est de 2^n - 1 coups, si bien que chaque disque ajouté double le travail : 4 disques demandent 15 coups, 6 en demandent 63, 8 en demandent 255.

Ici, le niveau facile compte 4 disques sur trois tiges, le niveau moyen 6 disques, et le niveau difficile est la version à quatre tiges que Henry Dudeney proposa en 1907 dans The Canterbury Puzzles sous le nom de « The Reve's Puzzle » : huit fromages de tailles différentes sur quatre tabourets. Une quatrième tige raccourcit beaucoup le trajet, 33 coups pour huit disques, mais le rend bien plus difficile à voir. Chaque jour, il y a aussi une tour du jour : six disques éparpillés sur trois tiges, les mêmes pour tous, à rassembler sur la tige au bouton doré.

Comment jouer

Amenez tous les disques sur la tige au bouton doré.

• Touchez une tige pour soulever son disque du haut : il flotte au-dessus de la tige. Touchez une autre tige pour l'y poser, ou sa propre tige pour le remettre en place.
• Faites glisser un disque du doigt jusqu'à une autre tige et relâchez.
• Au clavier, les touches 1 à 4 choisissent les tiges, les flèches passent de l'une à l'autre, et Échap repose un disque soulevé.
• La seule règle. Un disque ne se pose que sur une tige vide ou sur un disque plus grand. Si vous essayez autrement, le disque fait non de la tête et le disque plus petit qui gêne s'allume.
• Les étoiles. Trois pour le nombre minimum de coups de la tour, deux jusqu'à environ un quart de plus, une au-delà. Les étoiles en haut montrent le maximum que vous pouvez encore obtenir depuis votre position.
• Annuler existe au niveau facile et retire votre dernier coup du compte. Le chronomètre continue.
• Indice. Soulève le disque qu'un plus court chemin déplace ensuite et éclaire la tige où il va, pour 20 secondes sur votre score.
• Le score. Votre temps depuis le premier coup, plus 5 secondes par coup au-delà du minimum et 20 secondes par indice. Plus il est bas, mieux c'est.

Conseils de stratégie

1. Pensez en tours, pas en disques. Pour déplacer une tour de six, mettez d'abord les cinq disques au-dessus du plus grand sur la troisième tige, puis le plus grand passe en un seul coup, et les cinq le suivent. Chaque tour plus petite se déplace de la même façon.
2. Le plus petit disque joue un coup sur deux. Dans une solution parfaite sur trois tiges, un coup sur deux est celui du plus petit disque, qui tourne toujours dans le même sens d'une tige à l'autre. Le coup intermédiaire est le seul coup permis qui ne le touche pas.
3. Pair ou impair décide du premier coup. Avec un nombre pair de disques, le plus petit va d'abord sur la tige du milieu ; avec un nombre impair, directement sur la cible.
4. Tours éparpillées : commencez par le plus grand. Trouvez le plus grand disque qui n'est pas encore sur la cible. Tous les plus petits doivent se rassembler sur la troisième tige avant qu'il puisse bouger, et à partir de là, c'est de nouveau une tour ordinaire.
5. Quatre tiges : coupez la tour en deux. Mettez de côté les quatre ou cinq disques du haut en utilisant les quatre tiges, faites passer le reste avec les trois tiges encore libres, puis ramenez la partie haute. C'est la méthode de Frame et Stewart, et pour quatre tiges il est démontré qu'elle est la plus courte.

Questions fréquentes

Les Tours de Hanoï sont-elles gratuites ?

Oui. Comme tous les jeux de Play, elles se jouent gratuitement dans votre navigateur, sans téléchargement et sans compte.

Quel est le nombre minimum de coups ?

Pour n disques sur trois tiges, 2^n - 1 : 15 pour quatre disques, 63 pour six. Le nombre affiché en haut est le minimum pour la tour qui est devant vous, calculé par une recherche sur toutes les positions, il est donc juste aussi pour la tour du jour éparpillée.

Pourquoi le niveau difficile a-t-il quatre tiges ?

Huit disques sur trois tiges demandent 255 coups, et une fois la méthode connue, c'est plutôt une longue marche qu'un casse-tête. Avec quatre tiges, les mêmes huit disques ne demandent que 33 coups, mais le plus court chemin est bien plus difficile à trouver. J. S. Frame et B. M. Stewart ont décrit la méthode en 1941, et Thierry Bousch a démontré en 2014 qu'il n'existe pas de chemin plus court pour quatre tiges.

À quoi sert l'indice ?

Il soulève le disque qu'un plus court chemin déplace ensuite, où que soient vos disques, et éclaire la tige où il va. Touchez la tige éclairée pour jouer le coup. Chaque indice ajoute 20 secondes à votre score.

Qu'est-ce que la tour du jour ?

Chaque jour, tout le monde reçoit les mêmes six disques éparpillés sur trois tiges, avec la même tige cible, à 40 à 58 coups de l'arrivée par le plus court chemin, si bien que les temps se comparent directement dans le classement du jour.