Trois tiges, une pile de disques qui rétrécissent vers le haut, et une consigne qui tient en une phrase : déplacer toute la tour sur une autre tige. La tour de Hanoï a l’air d’un jouet d’éveil. Elle cache pourtant une méthode d’une régularité étonnante, que l’on peut appliquer les yeux presque fermés une fois qu’on l’a comprise. Voici la règle, la façon de résoudre le casse-tête en un nombre minimal de coups, et l’histoire assez savoureuse de son invention par un mathématicien français qui se faisait passer pour un mandarin.

La règle de la tour de Hanoï
Le matériel se compose d’un socle portant trois tiges et de plusieurs disques percés, tous de diamètres différents. Au départ, ils sont enfilés sur la tige de gauche, du plus grand en bas au plus petit en haut. Le but est de reconstruire la même tour sur une autre tige en respectant deux contraintes :
- on ne déplace qu’un seul disque à la fois, celui qui se trouve au sommet d’une pile ;
- on ne pose jamais un disque sur un disque plus petit que lui. Un disque se place sur une tige vide ou sur un disque plus large.
C’est tout. Ce qui corse l’affaire, c’est le nombre de coups, qui grimpe très vite à chaque disque ajouté.
Combien de coups faut-il ?
Le minimum est de 2n − 1 coups pour une tour de n disques. Le raisonnement se suit sans formule. Pour libérer le plus grand disque, il faut d’abord transporter tous les autres sur la tige intermédiaire. On déplace ensuite le grand disque, une seule fois, vers la tige d’arrivée. Il reste à reposer la petite tour par-dessus. Chaque disque ajouté double donc le travail précédent, plus un coup.
- 1 disque : 1 coup
- 2 disques : 3 coups
- 3 disques : 7 coups
- 4 disques : 15 coups
- 5 disques : 31 coups
- 8 disques, le format du jeu d’origine : 255 coups
Avec 64 disques, on arrive à 18 446 744 073 709 551 615 déplacements. À raison d’un coup par seconde, sans aucune erreur, cela représente environ 585 milliards d’années. Lucas lui-même faisait le calcul en siècles : » plus de cinq milliards de siècles « .
La méthode pour résoudre la tour sans réfléchir
Il existe une façon récursive de penser le problème (déplacer n − 1 disques, puis le grand, puis à nouveau n − 1 disques), mais elle oblige à garder en tête une pile de tâches inachevées. Pour jouer à la main, une autre méthode est bien plus confortable. Elle produit exactement la même suite de coups, donc la solution la plus courte.
Elle repose sur deux gestes qui alternent :
- Un coup sur deux, on déplace le plus petit disque, toujours dans le même sens de rotation, en imaginant que les trois tiges sont disposées en cercle (après la tige de droite, on revient à celle de gauche).
- L’autre coup, on déplace le seul disque possible qui n’est pas le plus petit. Il n’y a jamais d’hésitation : entre les deux tiges qui ne portent pas le petit disque, un seul mouvement respecte la règle.
Reste à choisir le sens de rotation du petit disque. Si vous partez de la tige A et voulez finir sur la tige C, le petit disque tourne A → C → B → A quand le nombre de disques est impair, et A → B → C → A quand il est pair. Si vous partez dans le mauvais sens, rien de grave : la tour se reconstruira simplement sur la tige B, toujours en un nombre minimal de coups.
Exemple pas à pas avec trois disques
Numérotons les disques 1 (le petit), 2 et 3 (le grand). Trois disques, c’est un nombre impair : le disque 1 tourne donc dans le sens A → C → B.
- Disque 1 de A vers C.
- Seul coup possible hors du petit disque : disque 2 de A vers B.
- Disque 1 de C vers B, sur le disque 2.
- Seul coup possible : disque 3 de A vers C.
- Disque 1 de B vers A.
- Seul coup possible : disque 2 de B vers C, sur le disque 3.
- Disque 1 de A vers C. La tour est reconstruite en 7 coups.
Faites l’essai avec quatre disques en inversant le sens du petit disque (A → B → C) : vous arrivez sur C en 15 coups. Ce petit truc a une histoire. Lucas l’attribue, dès 1884, à son jeune parent Raoul Olive, alors lycéen à Charlemagne : il faut » faire continuellement tourner le disque le plus petit, toujours dans le même sens « , un coup sur deux.
Deux réflexes pour ne pas se perdre
Si vous êtes perdu au milieu d’une partie, regardez où se trouve le petit disque et quel était son dernier mouvement : s’il vient de bouger, c’est au tour d’un autre disque. Ne déplacez jamais le petit disque deux fois de suite, ni un autre disque deux fois de suite : dans la solution la plus courte, cela n’arrive jamais.
Pour un enfant ou un débutant, commencez avec trois disques seulement, puis ajoutez-en un à la fois. On voit alors apparaître la logique de doublement, et la tour de huit disques devient une affaire de patience plutôt que de calcul.
La vraie histoire : un mandarin venu d’Amiens
Le jeu ne vient ni d’Asie ni d’un temple ancien. Il a été inventé par Édouard Lucas (1842-1891), mathématicien français connu pour ses travaux sur les nombres, et commercialisé en 1883 sous un titre délicieusement mystificateur : » La Tour d’Hanoï, véritable casse-tête annamite, jeu rapporté du Tonkin par le professeur N. Claus (de Siam), mandarin du collège Li-Sou-Stian « .
Le déguisement n’a pas tenu longtemps. Fin décembre 1883, le journaliste scientifique Henri de Parville, qui avait reçu une boîte par la poste, remarque dans le Journal des débats qu’en permutant les lettres on obtient » Lucas d’Amiens, professeur du lycée Saint-Louis « . » N. Claus de Siam » est l’anagramme de » Lucas d’Amiens « , sa ville natale, et Li-Sou-Stian celle de Saint-Louis, le lycée parisien où il enseignait.
La notice de 1883 racontait une légende inventée de toutes pièces : dans le grand temple de Bénarès, des prêtres déplaceraient jour et nuit une tour sacrée de 64 disques d’or selon les mêmes règles, et la fin du monde surviendrait à la dernière étape. Lucas proposait même, par jeu, une prime à quiconque réaliserait le transport à la main, sans risque de devoir la verser. Dans un fascicule publié en 1889, il passe aux aveux : le jeu » n’a pas été rapporté du Tonkin « , il a été imaginé en 1876 à Paris, rue Monge.
Pourquoi Hanoï ? Lucas ne l’a pas expliqué. Les auteurs du livre de référence sur le sujet, Andreas M. Hinz, Sandi Klavžar et Ciril Petr, rapprochent le nom de l’actualité coloniale de l’époque : la prise de Hanoï en 1882 et le traité de Hué de 1883, qui établit le protectorat français sur l’Annam et le Tonkin. C’est une hypothèse, pas une certitude.
On ne connaît pas avec certitude l’éditeur de la première boîte. Un brevet portant ce titre a été délivré en 1883 à la maison parisienne Grasson et Dupuy, alors que la boîte de 1883 ne porte pas de nom d’éditeur. En 1888, Lucas a donné au Conservatoire national des arts et métiers deux exemplaires, aujourd’hui au Musée des arts et métiers : le modèle classique à trois tiges et huit disques, et une version à six tiges. Le jeu a ensuite été repris par plusieurs fabricants, parfois sous le nom de » Tour de Brahma « .
Des variantes pour aller plus loin
Quand la tour à trois tiges ne résiste plus, d’autres versions changent complètement le problème :
- Quatre tiges. Le casse-têtiste anglais Henry Ernest Dudeney en a fait une énigme avec des fromages empilés sur quatre tabourets, le » Reve’s Puzzle » de ses Canterbury Puzzles. Une méthode générale, l’algorithme de Frame-Stewart, est publiée en 1941, mais la preuve qu’elle donne bien le minimum de coups avec quatre tiges n’a été établie qu’en 2014 par le mathématicien Thierry Bousch.
- Plusieurs couleurs. Lucas proposait dès 1889 une tour à cinq tiges et seize disques de quatre couleurs, avec des problèmes de tri à résoudre selon les mêmes règles.
- Le lien avec le binaire. Lucas présentait sa tour comme une illustration de la numération binaire, au même titre que le baguenaudier. La suite des coups correspond au code binaire réfléchi, dit code de Gray : à chaque coup, un seul disque change de place, comme un seul chiffre change entre deux nombres consécutifs de ce code.
La tour de Hanoï s’est aussi installée dans d’autres univers. Elle sert d’exemple classique pour enseigner la récursivité en programmation. En psychologie, Jean-François Richard l’a proposée à plus de 1 400 enfants de 7 ans pour une étude publiée en 1982 dans L’Année psychologique sur la manière dont la planification apparaît pendant la résolution.
Bien choisir une tour de Hanoï en bois

Premier piège : beaucoup d’anneaux à empiler pour les tout-petits ressemblent à une tour de Hanoï, mais n’ont qu’une tige. Ce sont de bons jouets de tri et de motricité, pas le casse-tête de Lucas. Vérifiez la présence de trois tiges (ou plus pour les variantes) et de disques tous de diamètres différents.
Quelques points à regarder ensuite :
- Le nombre de disques. Sept ou huit disques permettent déjà de varier la difficulté, et huit correspond au jeu d’origine. Un modèle dont on peut retirer des disques permet de commencer à trois.
- Le jeu entre disques et tiges. Les disques doivent coulisser sans forcer ni rester coincés. Des tiges assez hautes pour accueillir toute la tour évitent qu’elle bascule.
- Un socle stable, assez long pour que les trois piles ne se touchent pas.
- Les couleurs. Des disques qui alternent deux couleurs aident à repérer les erreurs : dans la solution la plus courte, on ne pose jamais un disque sur un autre de la même couleur.
- L’âge et le bois. Fiez-vous au marquage d’âge et aux avertissements du fabricant, pas à l’apparence du jeu. Si la provenance du bois compte pour vous, notre article sur les labels FSC et PEFC des jouets en bois explique ce que ces certifications garantissent.
Compacte et silencieuse, une tour de Hanoï a aussi sa place parmi les jeux à emporter en vacances, à condition de bien ranger les disques pour le voyage.
Pour aller plus loin
La tour de Hanoï appartient à la famille des casse-têtes de déplacement, présentée avec le tangram, le cube Soma et les burrs dans notre guide des casse-têtes en bois et de leurs grandes familles. Son cousin le plus proche est sans doute le taquin, auquel Lucas a consacré un chapitre de ses Récréations mathématiques. Si vous aimez les jeux où la logique pure décide de tout, essayez le Quarto, cette fois à deux joueurs. Et pour d’autres objets simples qui traversent les générations, voyez le retour de la toupie, du bilboquet et du yoyo.
Une question reste ouverte : combien de temps vous faut-il pour une tour de huit disques, sans regarder la méthode ?
Sources
- Michel Boutin, » Les jeux dans les collections du Conservatoire national des arts et métiers, 4 : la Tour d’Hanoï et le baguenaudier « , Le Vieux Papier, fascicule 431, janvier 2019, copie en ligne (PDF) : titre de 1883, chronique d’Henri de Parville, aveux de Lucas en 1889, remarque de Raoul Olive, brevet de 1883, exemplaires du Cnam, étude de J.-F. Richard.
- The Puzzle Museum, Eduardo Lucas : La Tour d’Hanoi : boîte et notice originales de 1883, anagrammes, légende de Bénarès.
- MacTutor, université de St Andrews, The Towers of Hanoi.
- Wikipédia, Tours de Hanoï et Tower of Hanoi : méthode itérative, sens de rotation du petit disque, quatre tiges (Frame-Stewart 1941, Bousch 2014).