Tour de Hanoï : le casse-tête de Lucas

Le casse-tête réunit trois tiges et une pile de disques percés, tous de tailles différentes, empilés du plus grand au plus petit. Il s'agit de transporter la pile entière de la tige de départ, A, à la tige d'arrivée, C, en s'aidant de la tige intermédiaire, B. Chaque coup déplace un disque à la fois, pris au sommet d'une tige, et jamais un disque ne se pose sur un plus petit.

À l'écran, toucher ou cliquer une tige soulève son disque du sommet, et toucher une autre tige l'y pose. Faire glisser le disque marche aussi. Au clavier, une tige sélectionnée avec Tab répond aux chiffres de 1 à 3, ou de 1 à 4 avec quatre tiges, et aux lettres A à D. La première touche soulève, la seconde pose. Échap repose le disque soulevé, et les flèches passent d'une tige à l'autre.

Un coup interdit est refusé avec sa raison, par exemple « Le disque 2 ne peut pas aller sur le disque 1 ». Le plateau tremble alors, sauf si les animations réduites sont activées. Trois compteurs suivent la partie. « Coups » compte les déplacements sur le plateau, et une annulation en retire un. « Minimum possible » donne le nombre minimal de coups pour la tour choisie, et « Temps » court du premier coup à la tour complète.

Une première partie se joue avec 4 disques et trois tiges, soit 15 coups au mieux. Le bouton « Annuler » reprend autant de coups que voulu ; chacun est compté parmi les coups annulés. À la fin, le résultat compare vos coups au minimum et affiche le temps au dixième de seconde. « Copier le résultat » copie une ligne de texte avec le lien, et un bouton propose aussitôt un disque de plus.

Il faut 2ⁿ − 1 coups au minimum pour déplacer n disques, soit 31 avec 5 disques, 255 avec 8 et 1 023 avec 10. À un coup par seconde, sans hésitation, une tour de 10 disques occupe donc 17 min 3 s.

Édouard Lucas le formulait déjà dans le tome 3 de ses Récréations mathématiques, en 1893 : chaque disque ajouté double le nombre de coups et en ajoute un. Son jeu d'origine, à 8 disques, demandait ainsi 255 coups, soit plus de quatre minutes au rythme d'une seconde par coup, écrivait-il.

Le 23 octobre 2026, jour de la vérification de cette page, Guinness World Records attribuait le record de la tour à 6 disques à Lim Kai Yi. Le temps retenu est de 22,26 secondes, le 15 novembre 2024. Cela fait au moins 63 coups, environ 2,8 par seconde. Les cas de référence, dont la table de Lucas, ouvrent le jeu sur la tour correspondante.

La méthode la plus simple suit le plus petit disque : il se déplace tous les deux coups, toujours dans le même sens autour des tiges. Entre deux de ses déplacements, un seul coup légal le laisse en place. Des deux autres disques du sommet, seul le plus petit peut en effet aller sur le plus grand, ou sur une tige vide.

Lucas attribue cette solution itérative à son neveu Raoul Olive, élève du lycée Charlemagne. Il la résume ainsi : « le disque le plus petit tourne toujours dans le même sens de deux en deux coups ». Avec un nombre impair de disques, il part vers C et visite A, C et B, puis recommence. Avec un nombre pair, il part vers B et visite A, B et C.

Avec 5 disques, le plus petit bouge 16 fois, le suivant 8, puis 4, 2 et 1 pour le plus grand. Chaque disque bouge deux fois moins que le disque immédiatement plus petit. Les disques déplacés suivent la suite 1, 2, 1, 3, 1, 2, 1, 4, et ainsi de suite. Au coup m, c'est le disque dont le numéro vaut un de plus que le nombre de zéros qui terminent m écrit en binaire, d'après une remarque d'A. M. Hinz dans la suite A001511 de l'OEIS.

Voici les 31 coups pour 5 disques, de la tige A vers la tige C. Le disque 1 est le plus petit, et chaque ligne donne la tige de départ puis celle d'arrivée.

Dans le jeu, le panneau « La solution coup par coup » donne la même liste pour la tour choisie. Il surligne le prochain coup tant que la partie la suit. « Imprimer la liste des coups » n'imprime que cette liste, pour jouer avec un vrai jeu à côté.

Il faut au moins 2ⁿ − 1 coups pour déplacer une tour de n disques. Le plus grand disque ne peut bouger qu'une fois tous les autres empilés sur la troisième tige. Il faut donc déplacer les n − 1 disques du dessus, puis le grand disque, puis de nouveau les n − 1 disques. En notant u(n) le nombre minimal de coups, on obtient u(n) = 2 u(n − 1) + 1, avec u(1) = 1. Ainsi u(n) + 1 = 2 (u(n − 1) + 1) : la suite u(n) + 1 est une suite géométrique de raison 2, égale à 2ⁿ. On trouve 7 coups pour 3 disques et 31 pour 5.

Un raisonnement par récurrence établit les deux points : la formule elle-même et l'impossibilité de faire mieux. Le disque du bas doit en effet attendre que la troisième tige porte tous les autres. Plus magazine, de l'université de Cambridge, détaille cette preuve, et le chapitre que Robert Sedgewick et Kevin Wayne consacrent à la récursivité, à Princeton, en tire le même compte.

Les valeurs 1, 3, 7, 15, 31 et 63 appartiennent à la suite A000225 de l'OEIS : ce sont les puissances de deux diminuées de un. Avec 10 disques, on arrive à 1 023, et chaque disque de plus repousse ce total au double, plus un.

La récursivité consiste à résoudre un problème en appliquant la même méthode à un problème plus petit, jusqu'à un cas de base qui se règle directement. Le chapitre de Princeton sur la récursivité prend le casse-tête comme exemple, et son algorithme récursif tient en trois étapes.

1. Déplacer les n − 1 disques du dessus vers la tige intermédiaire, avec la même méthode.
2. Déplacer le plus grand disque vers la tige d'arrivée.
3. Ramener les n − 1 disques sur lui, toujours avec la même méthode.

Le cas de base est une tour d'un seul disque, posée en un coup. Chaque appel produit un coup de plus que ses deux sous-appels réunis, ce qui redonne la récurrence de la preuve. Les coups obtenus sont ceux de la solution itérative, dans le même ordre.

En France, le programme de numérique et sciences informatiques (NSI) de terminale est paru au BO spécial n° 8 du 25 juillet 2019. Il inscrit la récursivité parmi ses contenus, sans citer le casse-tête. La ressource Éduscol « Récursivité » de juillet 2021 en fait en revanche un projet. Elle présente la légende comme très ancienne, alors que Lucas l'a inventée avec le jeu.

Toute disposition où, sur chaque tige, les disques rapetissent vers le haut est une position légale, et n disques en admettent 3ⁿ, soit 81 avec 4 disques. Chaque disque choisit sa tige, et l'ordre sur une tige est imposé par les tailles.

L'option « Une position aléatoire » tire une position au hasard, toutes également probables, sauf que le plus gros disque ne part jamais de la tige C. Le compteur devient alors « Minimum depuis le départ ». Ce disque doit donc bouger : avec 4 disques, il faut entre 8 et 15 coups, 12,7 en moyenne d'après le calcul du site. Sur toutes les positions, la moyenne vaut les deux tiers de 2ⁿ − 1, soit 10 coups pour 4 disques : c'est un décompte exhaustif propre au site.

La position tirée s'inscrit dans le lien de la page, par exemple ?start=random&pos=ABCA, si bien qu'un lien partagé donne le même départ. Le tirage n'a lieu qu'après un geste de votre part, et ces parties ne comptent jamais parmi les meilleurs résultats.

« Indice » montre le prochain coup d'une solution la plus courte, d'où que partent les disques. Les deux tiges s'éclairent et une phrase précise le coup, comme « Indice : déplacez le disque 2 de A vers C ». Chaque indice est compté. « Résoudre » laisse le solveur finir depuis la position actuelle, avec 0,9 seconde entre deux coups en vitesse lente, 0,45 en normale et 0,16 en rapide.

Avec « Pause », « Un coup » et « Prendre la main », on suit le solveur coup par coup ou l'on reprend la partie à sa place. Quand une partie commencée sur une tour suit la solution affichée, le solveur la poursuit.

Relier chaque position à celles qu'un coup permet d'atteindre dessine un graphe qui ressemble de plus en plus au triangle de Sierpiński à mesure que les disques s'ajoutent. Plus magazine le montre en 2012, comme le livre The Tower of Hanoi: Myths and Maths d'Andreas M. Hinz, Sandi Klavžar et Ciril Petr.

Édouard Lucas, mathématicien français, a publié le casse-tête en 1883, sous un nom d'emprunt : « professeur N. Claus (de Siam), mandarin du collège Li-Sou-Stian ». Selon MacTutor, le site d'histoire des mathématiques de l'université de St Andrews, N. Claus de Siam est l'anagramme de Lucas d'Amiens, et Li-Sou-Stian celle de Saint Louis.

Le lycée Saint-Louis est l'établissement où Lucas enseignait alors. Anne-Marie Décaillot, dans la Revue d'histoire des mathématiques, situe son arrivée en octobre 1879. Il venait du lycée Charlemagne, où il enseignait depuis 1876 et où il revient en 1890.

D'après le Journal des Débats du 27 décembre 1883, cité par R. E. Allardice et A. Y. Fraser, la boîte vendait « la Tour d'Hanoï, véritable casse-tête annamite ». Lucas écrira pourtant que le jeu n'a pas été rapporté du Tonkin, « quoi qu'en dise le prospectus ». Dans ses Récréations mathématiques, il décrit « huit pions en bois percés à leur centre », enfilés sur trois clous fixés à une tablette.

Lucas a aussi décrit la pipopipette, d'abord sous le titre « le jeu de l'École Polytechnique » en 1883, puis sous ce nom en 1889.

La légende accompagnait le jeu dès 1883. Dans le grand temple de Bénarès, en Inde, des prêtres, les brahmes, déplacent une tour de 64 disques d'or pur entre trois aiguilles de diamant. Ils suivent les mêmes règles : un disque à chaque fois, jamais un grand sur un petit. Le jour où ils auront fini, la tour et les brahmes tomberont, et ce sera la fin du monde.

Lucas reprend le récit dans le tome III de ses Récréations mathématiques, sous le titre « Les brahmes tombent ! ». C'est une histoire inventée, ni ancienne, ni vietnamienne, ni tibétaine : il écrit que le jeu et sa légende ont été imaginés au 56 de la rue Monge, à Paris. Henri de Parville l'a racontée dans La Nature en 1884, comme le rappelle W. W. Rouse Ball en 1914.

Pour 64 disques, la solution compte 2⁶⁴ − 1 coups, soit 18 446 744 073 709 551 615. Lucas imprime ce nombre de 20 chiffres en entier.

Les psychologues emploient des tâches de tours pour étudier la planification et la résolution de problèmes. Plus magazine note qu'on y voit les gens réfléchir. En 1982, Tim Shallice décrivait une tâche de planification. Une étude de l'université Érasme de Rotterdam présente la tour de Londres comme un instrument très utilisé pour mesurer cette capacité.

Jeremy Sullivan, Cynthia Riccio et Candace Castillo ont passé en revue en 2009 ces tâches de tours comme mesures des fonctions exécutives. Le dossier de la Cité des sciences et de l'industrie sur les fonctions exécutives présente lui aussi la tour de Londres comme une épreuve de planification.

Cette page reste un casse-tête : ses compteurs n'ont aucune valeur clinique et ne mesurent ni l'intelligence, ni l'attention, ni aucun trouble. Un test neuropsychologique suit un protocole et des normes que ce jeu n'a pas. Le test de Stroop, autre épreuve classique de psychologie, se joue aussi sur le site, avec la même réserve.