HISTOIRE · 2026-06-29
La Tour de Hanoï (1883) — Un héritage récursif inscrit dans 64 disques sans fin
Le jouet en bois qu'Édouard Lucas lança sous pseudonyme, et le 2ⁿ−1 tapi derrière
Introduction
C'est un jouet de 1883. Trois tiges dressées, et sur l'une d'elles des disques de tailles différentes empilés du plus grand au plus petit. Les règles sont au nombre de deux — on ne peut déplacer qu'un seul disque à la fois, et on ne peut pas poser un disque plus grand sur un disque plus petit. Dans ces contraintes, transférez la tour entière sur une autre tige. Ce jeu, simplement cela, survit encore aujourd'hui dans les salles de classe et les boîtes à jouets du monde entier sous le nom de « Tour de Hanoï ».
L'apparence est entièrement sobre. Des tiges en bois, quelques anneaux. Même un enfant peut apprendre les règles en une minute. Mais si je prends ce jouet comme objet d'étude historique, c'est parce que derrière cette sobriété se trouvait déjà, en forme achevée, la structure que l'informatique du siècle suivant allait appeler « récursion ». En 1883, on tenait déjà cette structure entre les mains sous la forme d'un jouet qu'on pouvait toucher du doigt.
Cet article suit la véritable identité du mathématicien qui inventa cette tour, la grande fiction dont il l'entoura, et le poids du nombre 2ⁿ−1 que déduisent les règles simples. Non par nostalgie. Mais pour vérifier de quelle antiquité proviennent les concepts d'« imbrication » et d'« espace d'états » que les puzzles contemporains utilisent comme allant de soi.
Trois tiges et la tour d'or — le jouet de 1883 (image · généré par IA)
Le contexte de l'époque
Paris, 1883. L'inventeur est le mathématicien Édouard Lucas (1842–1891). Mais quand le jouet parut au monde, son auteur était désigné par « N. Claus (de Siam), professeur à l'académie de Li-Sou-Stian ». C'était un leurre. « N. Claus (de Siam) » est une anagramme de « Lucas (d'Amiens) », et « Li-Sou-Stian » est une transposition des lettres du prestigieux Lycée Saint-Louis de Paris, où il enseignait alors. Ce stratagème fut rapidement percé à jour par le chroniqueur scientifique Henri de Parville.
Lucas ne fabriquait pas des jouets en dilettante. C'était un chercheur sérieux en théorie des nombres, dont le nom demeure associé aux « suites de Lucas » et au « test de Lucas–Lehmer ». L'Europe de l'époque possédait une riche tradition des « récréations mathématiques », qui transmettaient les propriétés des nombres par le jeu, et la Tour de Hanoï s'inscrivait dans cette filiation. Cette tour figure aussi dans l'ouvrage homonyme de Lucas lui-même.
Le jouet était accompagné d'une histoire grandiose. Des moines, disait-on, déplaçaient sans cesse 64 disques d'or sur trois aiguilles de diamant dans un temple de Bénarès (aujourd'hui Varanasi), en Inde, et le monde s'effondrerait à l'achèvement de cette tâche. C'est naturellement une fiction. Mais je ne la minimise pas. Cette façon de conférer le poids du mythe à la froideur des chiffres est le prototype même de la « mise en scène » que les créateurs de puzzles ultérieurs allaient répéter.
La boîte sur la table et le billet au pseudonyme — contexte de l'époque (image · générée par IA)
Les mécaniques
Les règles n'ont pas changé depuis 1883. Un seul disque à la fois. On ne peut pas poser un grand disque sur un petit. La tige vide est libre d'utilisation. Ces trois seules contraintes définissent la tâche de déplacer la tour. On peut « à peu près s'en sortir » en la manipulant à la main, mais dès qu'on cherche le nombre minimum de mouvements, la structure se révèle.
Cette structure, c'est la récursion. Pour déplacer n disques de A vers C : on retire d'abord les n−1 disques supérieurs vers B, on déplace le plus grand disque de A vers C, puis on transfère les n−1 disques mis en attente en B vers C. Le problème se décompose en deux instances identiques de taille légèrement inférieure. Le nombre de mouvements T(n) satisfait la relation T(n)=2·T(n−1)+1, et la résoudre donne exactement T(n)=2ⁿ−1. 1 disque : 1 mouvement. 3 disques : 7 mouvements. 10 disques : 1 023 mouvements. La solution optimale n'est pas unique, mais le nombre optimal de mouvements est entièrement déterminé par cette formule.
Revenons à la légende. Avec 64 disques, on obtient 2⁶⁴−1, soit environ 1,8 × 10¹⁹ mouvements. Même si les moines déplaçaient un disque par seconde sans jamais s'arrêter, il leur faudrait environ 585 milliards d'années — soit environ 42 fois l'âge estimé de l'univers. La menace selon laquelle « le monde finira quand la tour sera terminée » traduit en langage mythique l'immensité de la fonction exponentielle. Des règles simples engendrent des nombres explosifs. C'est cet écart qui constitue le plaisir central que vendent encore aujourd'hui les puzzles de réflexion.
La décomposition récursive et la conclusion 2ⁿ−1 (image · générée par IA)
Filiation jusqu'à nos jours
C'est dans l'informatique du XXe siècle que le jouet de 1883 a planté ses racines les plus profondes. La Tour de Hanoï est devenue un exercice quasi standard pour enseigner la récursion en programmation. Il n'existe guère d'exemple qui incarne aussi parfaitement, avec des règles aussi courtes, l'idée de récursion — « s'appeler soi-même avec une instance légèrement plus petite ». En même temps, cette tour est le tutoriel le plus lisible de la vision par « espace d'états », qui consiste à considérer chaque configuration comme un nœud et chaque mouvement légal comme une arête.
Je considère ce point de vue de l'« espace d'états » comme une clé pour lire les puzzles modernes. Concevoir l'ensemble d'une configuration comme un immense labyrinthe, et le parcourir par le chemin le plus court — l'analyse du Sokoban(仓库番) comme la calculabilité des taquins reposent sur cette vision. Ce que la Tour de Hanoï a apporté en 1883, c'est moins le jouet lui-même qu'une paire de lunettes pour regarder les puzzles de réflexion.
Pour illustrer un exemple contemporain qui fait frontalement du jeu avec les structures imbriquées, je lis Patrick's Parabox, sorti sur Steam en 2022, comme une prolongation de cette filiation. Des boîtes dans des boîtes, qui peuvent se contenir elles-mêmes — c'est un puzzle qui fait de la récursion même sa règle. L'auteur n'a pas déclaré s'être directement inspiré de la Tour de Hanoï. Mais la structure de base — « le même problème, réduit, s'imbrique » — était déjà présentée sous forme tangible par la tour en bois de 1883. La filiation n'est pas un certificat d'influence ; c'est la répétition d'une même structure à travers les époques.
De la tour d'or à l'imbrication contemporaine (image · générée par IA)
Références
Sources consultées pour cet article :
Conclusion
La tour de Bénarès continue de se déplacer, dans la légende. Le dernier mouvement, à 585 milliards d'années de distance, n'a naturellement jamais été effectué. Mais c'est précisément cette interminabilité qui constitue, selon moi, l'essence de ce que ce jouet a montré en 1883. Des règles simples, et un nombre de mouvements qui enfle exponentiellement. Dans un outil fini qu'on peut tenir entre les mains, se trouve pliée une infinité que nulle vie humaine ne pourrait épuiser.
Historiquement, ce que la Tour de Hanoï a légué, ce n'est pas telle ou telle solution particulière. C'est la récursion elle-même — l'idée qu'un problème peut se décomposer en copies plus petites de lui-même. Elle a émigré dans les manuels d'informatique, est devenue la lunette de l'espace d'états, et continue encore aujourd'hui d'éclairer de nouveaux puzzles. Les quelques anneaux empilés sur les tiges en bois de 1883 rappellent silencieusement combien les outils de la pensée ont des sources anciennes.
La nuit de Bénarès, la tour qui se déplace encore (image · générée par IA)
Reactions (no login)
Anonymous • one of each per visitor per day
