Tours de Hanoï : solution, formule 2^n - 1 et mathématiques du casse-tête

Par Dawid Siedlarz · · 10 min de lecture

Jouer à Tours de Hanoï gratuitement →

En bref : les tours de Hanoï avec n disques et trois tiges demandent au moins 2n − 1 coups : 7 pour 3 disques, 15 pour 4, 31 pour 5, 127 pour 7. Pour les résoudre, déplacez les n − 1 disques du haut vers la tige libre, le plus grand disque vers l'arrivée, puis les n − 1 disques par-dessus, ce qui est le même casse-tête en plus petit. La règle rapide : le plus petit disque bouge un coup sur deux, toujours dans le même sens, et entre-temps on joue le seul autre coup permis. Le casse-tête a été inventé par Édouard Lucas en 1883.

Les tours de Hanoï ont l'air d'un jouet : trois tiges et une pile de disques qui rétrécissent vers le haut. Il faut transporter toute la pile sur une autre tige, un disque à la fois, sans jamais poser un grand disque sur un plus petit. Avec 3 disques, cela prend une minute. Avec 7, il faut de la concentration. Avec 64, cela durerait plus longtemps que le Soleil. Derrière ce casse-tête si simple se cachent l'un des plus beaux exemples de récursivité en mathématiques, un compteur binaire et une fractale. D'abord la solution, ensuite les mathématiques.

Les règles

  1. Il y a trois tiges. Au départ, tous les disques sont sur une tige, le plus grand en bas.
  2. On déplace un disque à la fois : le disque du haut d'une tige va sur une autre tige.
  3. Un disque ne peut jamais être posé sur un disque plus petit.
  4. Le casse-tête est résolu quand toute la tour est sur la tige d'arrivée, dans le même ordre.

Dans notre jeu Tours de Hanoï, la tour part de la tige de gauche et doit finir sur celle de droite. Le niveau facile compte 3 disques, le moyen 5 et le difficile 7. Il n'y a pas de limite de temps, et le jeu affiche à côté de vos coups le minimum possible.

La solution à 3 disques, coup par coup

Appelons les tiges A (départ, à gauche), B (milieu) et C (arrivée, à droite), et les disques 1 (petit), 2 (moyen) et 3 (grand). La solution la plus courte compte 7 coups :

CoupDisqueDe → versEnsuite (A | B | C)
11A → C3 2 | – | 1
22A → B3 | 2 | 1
31C → B3 | 2 1 | –
43A → C– | 2 1 | 3
51B → A1 | 2 | 3
62B → C1 | – | 3 2
71A → C– | – | 3 2 1

Regardez la structure. Les coups 1 à 3 déplacent une tour de deux disques de A vers B. Le coup 4 déplace le grand disque. Les coups 5 à 7 reposent la tour de deux disques de B par-dessus. Tout le secret est là.

Deux façons de résoudre n'importe quelle tour

1. La méthode récursive (penser en tours)

Pour déplacer une tour de n disques de la tige de départ vers la tige d'arrivée :

  1. Déplacez les n − 1 disques du haut du départ vers la tige libre (la tige d'arrivée sert d'auxiliaire).
  2. Déplacez le plus grand disque du départ vers l'arrivée.
  3. Déplacez les n − 1 disques de la tige libre vers l'arrivée (le départ sert d'auxiliaire).

Les étapes 1 et 3 sont le même casse-tête avec un disque de moins : on leur applique donc les trois mêmes étapes, et ainsi de suite jusqu'à un seul disque, qu'on déplace tout simplement. C'est pourquoi les tours de Hanoï sont le premier exemple classique de récursivité dans les cours de programmation : une fonction qui résout un problème en s'appelant elle-même sur une version plus petite. C'est aussi la meilleure façon de comprendre une position : demandez-vous quel est le plus grand disque qui n'est pas encore à sa place ; tout ce qui est au-dessus doit aller sur la troisième tige.

2. La méthode itérative (sans rien planifier)

  1. À chaque coup impair (1er, 3e, 5e...), déplacez le plus petit disque d'une tige, toujours dans le même sens. Avec un nombre impair de disques, le sens est A → C → B → A (départ, arrivée, milieu) ; avec un nombre pair, A → B → C → A.
  2. À chaque coup pair, jouez le seul coup permis qui ne touche pas le plus petit disque. Il y en a toujours exactement un.

En suivant ces deux règles, vous finirez dans le nombre minimal de coups sans réfléchir à l'avance. C'est ainsi que la plupart des gens résolvent 7 disques. La méthode récursive est celle qui explique pourquoi ça marche.

Pourquoi le minimum est 2n − 1

Notons T(n) le nombre minimal de coups pour n disques. Le plus grand disque doit bouger au moins une fois. À ce moment-là, il doit être seul sur sa tige et la tige d'arrivée doit être vide : les n − 1 autres disques sont donc empilés sur la troisième tige, ce qui a demandé au moins T(n − 1) coups. Ensuite, ces disques doivent encore venir sur lui : de nouveau au moins T(n − 1) coups. Donc

T(n) = 2 × T(n − 1) + 1, avec T(1) = 1.

Cela donne 1, 3, 7, 15, 31, 63, 127... et chaque nombre vaut une puissance de deux moins un : T(n) = 2n − 1. La méthode récursive atteint exactement ce nombre, elle est donc optimale, et la solution la plus courte est même unique : il n'existe qu'une façon de réussir en 2n − 1 coups.

À quelle vitesse ça grandit

DisquesCoups minimumÀ un coup par seconde
377 secondes
41515 secondes
531environ une demi-minute
663environ 1 minute
7127environ 2 minutes
8255environ 4 minutes
101 023environ 17 minutes
201 048 575environ 12 jours
324 294 967 295environ 136 ans
6418 446 744 073 709 551 615environ 585 milliards d'années

Chaque disque ajouté double le travail. Voilà à quoi ressemble une croissance exponentielle, et c'est pourquoi ce casse-tête sert à l'enseigner.

Des motifs cachés

Quel disque bouge quand : un compteur binaire

Dans la solution la plus courte, le disque k (en comptant depuis le plus petit) bouge exactement 2n−k fois. Le plus petit fait la moitié de tous les coups (arrondie au supérieur) et le plus grand ne bouge qu'une fois, pile au milieu : après 3 coups avec 3 disques, après 15 avec 5, après 63 avec 7.

Il existe une règle encore plus jolie. Écrivez le numéro du coup en binaire et comptez les zéros à la fin : le coup 1 s'écrit 1 (aucun zéro, disque 1), le coup 2 10 (un zéro, disque 2), le coup 3 11 (disque 1), le coup 4 100 (deux zéros, disque 3). Le disque qui bouge porte toujours le numéro « nombre de zéros finaux plus un ». La solution est donc littéralement un compteur binaire de 0 à 2n − 1, et le numéro du coup suffit pour savoir quel disque déplacer. Cette même suite (1, 2, 1, 3, 1, 2, 1...) est l'ordre dans lequel les bits changent dans le code de Gray, une façon de compter en binaire où un seul bit change à chaque pas.

Une fractale : le triangle de Sierpiński

Chaque disque peut être sur n'importe laquelle des trois tiges, et l'ordre sur une tige est imposé (le plus grand en bas) : il y a donc exactement 3n positions permises, 27 pour 3 disques, 2 187 pour 7. Dessinez chaque position comme un point et reliez deux points quand un coup permis mène de l'une à l'autre : vous obtenez un triangle fait de trois triangles plus petits, eux-mêmes faits de trois plus petits, une version du triangle de Sierpiński. Les trois sommets sont les positions où toute la tour est sur une tige, et la solution la plus courte longe tout droit un des côtés.

Nos trois niveaux sont des nombres premiers

Les nombres de la forme 2n − 1 s'appellent nombres de Mersenne. Certains sont premiers, et c'est le cas des minimums de nos trois niveaux : 7, 31 et 127. Le dernier ramène à l'inventeur du jeu : en 1876, Édouard Lucas a démontré que 2127 − 1, un nombre de 39 chiffres, est premier. Il est resté le plus grand nombre premier connu pendant 75 ans, jusqu'en 1951, et le test de Lucas-Lehmer, fondé sur sa méthode, sert encore aujourd'hui à trouver les nombres premiers records.

Quatre tiges : un problème bien plus difficile

Avec une quatrième tige, on déplace la tour beaucoup plus vite, car il y a plus de places pour poser les disques. La version à quatre tiges a été publiée par Henry Dudeney dans The Canterbury Puzzles (1907) sous le nom de « The Reve's Puzzle ». En 1941, J. S. Frame et B. M. Stewart ont proposé, chacun de leur côté, une méthode : déplacer quelques disques du haut sur une tige libre en utilisant les quatre tiges, déplacer le reste avec les trois tiges restantes, puis remettre le premier groupe par-dessus. Le meilleur partage donne ces nombres de coups :

Disques3 tiges4 tiges (Frame-Stewart)
375
4159
53113
66317
712725
825533
101 02349

Pendant plus de 70 ans, personne n'a pu démontrer que cette méthode était la meilleure possible avec quatre tiges. Thierry Bousch l'a enfin prouvé en 2014. Pour cinq tiges ou plus, la question reste ouverte, ce qui est remarquable pour un casse-tête vendu comme jouet en 1883.

Histoire : Lucas, un pseudonyme et une légende

Le casse-tête est paru à Paris en 1883, attribué au « professeur N. Claus de Siam », du « collège Li-Sou-Stian ». Ce sont deux anagrammes : N. Claus de Siam donne Lucas d'Amiens, et Li-Sou-Stian donne Saint Louis, le lycée Saint-Louis où Édouard Lucas enseignait les mathématiques. Lucas (1842-1891) est aussi connu pour les nombres de Lucas, cousins de la suite de Fibonacci, et pour ses Récréations mathématiques en quatre volumes.

Le jeu était accompagné d'une légende : dans un grand temple, des prêtres déplacent une tour de 64 disques d'or entre trois aiguilles de diamant en suivant les deux mêmes règles, et quand ils auront fini, ce sera la fin du monde. Comme le montre le tableau ci-dessus, même à un coup par seconde et sans erreur, il leur faudrait environ 585 milliards d'années, plus de 40 fois l'âge de l'Univers. La légende, comme le nom de Hanoï, faisait partie de l'emballage exotique imaginé par Lucas, pas d'une tradition ancienne.

Où sert-on des tours de Hanoï aujourd'hui

  • Enseignement de la programmation. C'est l'exercice classique de récursivité ; la méthode en trois étapes devient une fonction de quelques lignes.
  • Enseignement des mathématiques. Relations de récurrence, raisonnement par récurrence, croissance exponentielle et numération binaire dans un seul casse-tête.
  • Psychologie. Les tâches de tours servent à étudier la planification et la résolution de problèmes : combien de coups à l'avance on réfléchit. Une variante, la tour de Londres, introduite par Tim Shallice en 1982, est utilisée en évaluation neuropsychologique.
  • Sauvegardes. Le schéma de rotation des bandes « tours de Hanoï » reprend le même motif 1, 2, 1, 3, 1, 2, 1 pour choisir quelle bande réécrire : les derniers jours sont couverts finement et les périodes plus anciennes de plus en plus largement.

Conseils pour notre jeu

  • Commencez au niveau facile et résolvez 3 disques avec la règle itérative jusqu'à ce qu'elle devienne automatique, puis passez à la méthode récursive avec 5 disques.
  • Avec un nombre impair de disques (tous nos niveaux : 3, 5, 7), le premier coup envoie le plus petit disque sur la tige de droite.
  • Vérifiez la mi-parcours : quand le plus grand disque bouge, tous les autres doivent être empilés sur la tige du milieu.
  • Ne déplacez jamais le plus petit disque deux fois de suite : c'est toujours un coup perdu.
  • Le score vaut 1 000 × coups minimum ÷ vos coups, multiplié par 1, 2 ou 4 selon le niveau ; une tour de 7 disques parfaite rapporte donc 4 000 points. Annuler un coup compte comme un coup.

Si vous aimez les casse-tête où il faut prévoir plusieurs coups à l'avance, essayez aussi Pousse-caisses (une variante du Sokoban) et le Taquin.

Questions fréquentes

Combien de coups faut-il au minimum pour les tours de Hanoï ?

Avec n disques et trois tiges, le minimum est 2 puissance n, moins 1 : 7 coups pour 3 disques, 15 pour 4, 31 pour 5, 63 pour 6 et 127 pour 7. Chaque disque supplémentaire double le nombre de coups et en ajoute un.

Comment résoudre les tours de Hanoï avec 3 disques ?

Avec les tiges A (départ), B (milieu) et C (arrivée) : petit disque de A vers C, moyen de A vers B, petit de C vers B, grand de A vers C, petit de B vers A, moyen de B vers C et petit de A vers C. Cela fait 7 coups, le minimum.

Quelle est l'astuce des tours de Hanoï ?

À chaque coup impair, déplacez le plus petit disque d'une tige, toujours dans le même sens (d'abord vers la tige d'arrivée si le nombre de disques est impair, vers celle du milieu s'il est pair). À chaque coup pair, jouez le seul coup permis qui ne touche pas le plus petit disque.

Combien de temps faudrait-il pour 64 disques ?

2 puissance 64, moins 1, soit 18 446 744 073 709 551 615 coups. À un coup par seconde sans la moindre erreur, environ 585 milliards d'années, à peu près 40 fois l'âge actuel de l'Univers.

Qui a inventé les tours de Hanoï ?

Le mathématicien français Édouard Lucas, qui l'a commercialisé en 1883 sous le pseudonyme N. Claus de Siam, anagramme de Lucas d'Amiens. Il l'a accompagné de la légende de prêtres déplaçant 64 disques d'or, après quoi viendrait la fin du monde.