Tour de Hanoï : la solution en 15 coups à 4 disques, pas à pas
Publié le

Pour résoudre la tour de Hanoï à 4 disques, il faut 15 coups au minimum, et il existe une méthode qui les donne un par un sans réfléchir : à chaque coup, on déplace le disque dont le numéro correspond au rang du dernier chiffre 1 du compteur écrit en binaire. Le tableau complet des 15 coups est plus bas, vérifié par un calcul pas à pas.
Les règles en deux lignes
Trois tiges, des disques de tailles croissantes empilés sur la première, le plus grand en bas. Il faut reconstruire la pile sur la troisième tige, en déplaçant un seul disque à la fois et sans jamais poser un disque sur un plus petit. Le casse-tête a été inventé par le mathématicien français Édouard Lucas et commercialisé en 1883 sous le titre « La Tour d’Hanoï, véritable casse-tête annamite », attribué à un « professeur N. Claus de Siam ». Ce pseudonyme est une anagramme de « Lucas d’Amiens » (Wikipédia, article « Tours de Hanoï »).
Pour s’entraîner sur la version en ligne, la page tour de Hanoï de TapisPlay propose de 3 à 8 disques et affiche en permanence le minimum de coups.
Combien de coups faut-il ?
Avec n disques, le minimum est 2n − 1 coups. Le raisonnement tient en une phrase : pour déplacer n disques, on déplace d’abord les n − 1 du dessus, puis le plus grand, puis on remet les n − 1 par-dessus. Le nombre de coups double donc, plus un, à chaque disque ajouté.
| Disques | Coups minimum |
|---|---|
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
Dans la légende de la notice du jeu, des brahmanes d’un temple de Bénarès déplaceraient la « Tour sacrée de Brahma », faite de 64 disques d’or, et la fin du monde viendrait avec le dernier coup. Le calcul donne 264 − 1, soit 18 446 744 073 709 551 615 coups. À un coup par seconde, avec une année de 365,25 jours, cela représente environ 584,5 milliards d’années, soit environ 42 fois l’âge estimé de l’Univers, un ordre de grandeur que reprend aussi Wikipédia.
La méthode du compteur binaire
C’est ici que la tour de Hanoï devient mécanique. La règle vient du lien avec le code de Gray binaire : selon Felix Herter et Günter Rote (conférence Fun with Algorithms, 2016), la suite des bits modifiés en comptant en binaire, 1, 2, 1, 3, 1, 2, 1, 4…, est exactement la suite des disques déplacés par l’algorithme récursif. On numérote les disques de 1 (le plus petit) à n (le plus grand), puis on compte les coups de 1 à 2n − 1 en binaire.
- Au coup k, on écrit k en binaire et on repère le dernier chiffre 1, en partant de la droite. Son rang donne le numéro du disque à déplacer : un 1 tout à droite (coup impair) désigne le disque 1, un 1 précédé d’un seul zéro désigne le disque 2, et ainsi de suite.
- Le disque 1 tourne toujours dans le même sens. Avec un nombre pair de disques, il va de la tige 1 à la tige 2, puis à la 3, puis revient à la 1. Avec un nombre impair, il va de la tige 1 à la 3, puis à la 2, puis revient à la 1.
- Tout autre disque n’a qu’un seul déplacement légal : on le pose sur l’unique tige où il peut aller, c’est-à-dire celle dont le disque du dessus est plus grand que lui, ou qui est vide.
Le disque 1 bouge donc un coup sur deux, le disque 2 un coup sur quatre, le disque 3 un coup sur huit. Le plus grand disque ne bouge qu’une fois, au coup du milieu : le coup 8 pour quatre disques, quand le compteur vaut 1000.
La solution complète pour 4 disques
Voici les 15 coups, générés puis rejoués étape par étape pour vérifier que chaque déplacement est légal et que la pile finit entière sur la tige 3.
| Coup | En binaire | Disque déplacé | De | Vers |
|---|---|---|---|---|
| 1 | 0001 | 1 | tige 1 | tige 2 |
| 2 | 0010 | 2 | tige 1 | tige 3 |
| 3 | 0011 | 1 | tige 2 | tige 3 |
| 4 | 0100 | 3 | tige 1 | tige 2 |
| 5 | 0101 | 1 | tige 3 | tige 1 |
| 6 | 0110 | 2 | tige 3 | tige 2 |
| 7 | 0111 | 1 | tige 1 | tige 2 |
| 8 | 1000 | 4 | tige 1 | tige 3 |
| 9 | 1001 | 1 | tige 2 | tige 3 |
| 10 | 1010 | 2 | tige 2 | tige 1 |
| 11 | 1011 | 1 | tige 3 | tige 1 |
| 12 | 1100 | 3 | tige 2 | tige 3 |
| 13 | 1101 | 1 | tige 1 | tige 2 |
| 14 | 1110 | 2 | tige 1 | tige 3 |
| 15 | 1111 | 1 | tige 2 | tige 3 |
Deux contrôles rapides. Le coup 8, binaire 1000, déplace le disque 4, le plus grand, de la tige 1 vers la tige 3 : à ce moment, les trois autres disques sont tous sur la tige 2. Et les coups impairs (1, 3, 5, 7, 9, 11, 13, 15) sont ceux du disque 1, qui suit bien le cycle 1, 2, 3, 1, 2, 3 des tiges.
Et pour 3 disques ?
Le sens du cycle s’inverse, car 3 est impair. Les 7 coups sont : disque 1 vers la tige 3, disque 2 vers la tige 2, disque 1 vers la tige 2, disque 3 vers la tige 3, disque 1 vers la tige 1, disque 2 vers la tige 3, disque 1 vers la tige 3.
Pourquoi on se trompe en jouant à l’instinct
Deux erreurs reviennent presque toujours. La première est de déplacer le disque 1 dans le mauvais sens pour la parité du nombre de disques : la pile finit alors sur la mauvaise tige ou la partie dépasse le minimum. La seconde est de déplacer deux fois de suite le même disque, ce qui gaspille un coup, puisqu’un seul déplacement aurait suffi. Si votre dernier coup concernait le disque 1, le coup suivant ne doit jamais le concerner : c’est la règle « un coup sur deux » qui vous protège.
Pour vérifier que vous avez compris, jouez 4 disques en visant exactement 15 coups, puis passez à 5 disques et 31 coups. Le jeu de TapisPlay évalue la partie par rapport à ce minimum, et propose une résolution automatique qui déroule la solution optimale depuis la position où vous êtes, pratique pour vérifier le tableau ci-dessus sur l’écran. Si vous aimez ce type de casse-tête où une règle simple cache une méthode, le taquin et Lights Out fonctionnent sur le même principe, et l’ensemble des jeux de logique et de réflexion gratuits est regroupé sur une seule page.
Questions fréquentes
Quelle est la formule du nombre minimum de coups ?
2n − 1, où n est le nombre de disques : 7 coups pour 3 disques, 15 pour 4, 31 pour 5.
Peut-on faire mieux que le minimum ?
Non. Le minimum est démontré : le plus grand disque ne peut bouger que lorsque tous les autres sont sur la tige intermédiaire, ce qui impose de déplacer deux fois la pile de n − 1 disques.
Le disque 1 doit-il toujours aller dans le même sens ?
Oui, pour la solution la plus courte. Avec un nombre pair de disques, le cycle des tiges est 1, 2, 3 ; avec un nombre impair, il est 1, 3, 2.
Combien de temps pour résoudre la version à 64 disques ?
À un déplacement par seconde, environ 584,5 milliards d’années, soit environ 42 fois l’âge estimé de l’Univers. La légende de la fin du monde ne risque donc pas de se réaliser par ce biais.
Sources
- Wikipédia en français, article « Tours de Hanoï » : invention par Édouard Lucas, pseudonyme N. Claus de Siam, légende des 64 disques, formule 2^n − 1, durée de 584,5 milliards d’années, consulté en octobre 2026, fr.wikipedia.org
- Wikipedia, article « Tower of Hanoi » : édition de 1883, anagramme de « Lucas d’Amiens », légende de Bénarès, solution par le code de Gray, sens de rotation du plus petit disque, consulté en octobre 2026, en.wikipedia.org
- Felix Herter et Günter Rote, « Loopless Gray Code Enumeration and the Tower of Bucharest », 8th International Conference on Fun with Algorithms (FUN 2016), LIPIcs vol. 49, article 19, 2016, drops.dagstuhl.de