Calculatrice des Tours de Hanoï

Ce que cela représente vraiment

Les nombres ci-dessus sont exacts et, seuls, ils n'apprennent presque rien : passé quelques milliards, un très grand nombre ressemble beaucoup à un autre. Ce que fait vraiment l'arithmétique se voit mieux qu'il ne se raconte. Comme chaque disque supplémentaire double le travail, une règle aux disques régulièrement espacés est une règle aux durées qui se multiplient — et toute la distance entre une pause café (dix disques, dix-sept minutes) et l'âge de l'univers (cinquante-neuf disques) tient en une cinquantaine de pas.

• 1 disque — 1 coup — 1 seconde : la première taille qui atteint une seconde.
• 6 disques — 63 coups — 1 minute : la première taille qui atteint une minute.
• 12 disques — 4 095 coups — 1 heure : la première taille qui atteint une heure.
• 17 disques — 131 071 coups — 1 jour : la première taille qui atteint un jour.
• 25 disques — 33 554 431 coups — 1 an : la première taille qui atteint un an.
• 32 disques — 4 294 967 295 coups — 136 ans : la première taille qui atteint une vie humaine.
• 38 disques — 274 877 906 943 coups — 8,71 mille ans : la première taille qui atteint toute l'histoire écrite.
• 59 disques — 576 460 752 303 423 487 coups — 18,3 milliards d'années : la première taille qui atteint l'âge de l'univers.

La bande ombrée, vers la gauche, est tout ce que vous pouvez réellement jouer ici. Onze disques font une longue séance ; vingt-cinq font une année de coups sans interruption ; cinquante-neuf dépassent l'âge de l'univers. Rien dans les règles ne change le long de cet axe : seul le compte change.

La formule

Une partie parfaite de n disques prend exactement 2ⁿ − 1 coups — la formule des Tours de Hanoï, qu'on écrit aussi 2^n − 1 faute d'exposants. Ce n'est pas le meilleur résultat obtenu à ce jour, c'est un plancher démontré. Pour que le plus grand disque puisse bouger, tous les disques plus petits doivent être empilés à l'écart sur la tour intermédiaire, et une fois qu'il a traversé, ils doivent tous revenir par-dessus. Deux transferts complets de n − 1 disques, plus un coup :

T(n) = 2·T(n − 1) + 1, en partant de T(0) = 0 — pas de disque, pas de coup.

1. 1Déplacer les n−1 disques du dessus vers la tour intermédiaire. Rien d'autre n'est possible tant qu'ils sont là.

2. 2Le plus grand disque est libre, et sa tour d'arrivée est vide. Il passe en un seul coup — le seul dont cette phase a besoin.

3. 3Reconstruire la pile de n−1 disques par-dessus. C'est le même problème avec un disque de moins, jusqu'à un disque unique qui se déplace en un coup.

En déroulant, on obtient 1, 3, 7, 15, 31, 63 — chacun le double du précédent plus un, c'est-à-dire la suite des nombres situés juste en dessous d'une puissance de deux. Chaque disque ajouté fait un peu plus que doubler le travail, et c'est pourquoi le casse-tête passe d'une pause café à plus que l'âge de l'univers en moins de cinquante pas.

Cette même récurrence explique la réputation du casse-tête dans les cours d'informatique. Puisque le travail double à chaque disque, la solution récursive s'exécute en temps O(2ⁿ) — et aucun algorithme plus malin ne se cache derrière : le nombre de coups est lui-même exponentiel, et chaque coup doit être produit. Ce qu'elle ne coûte pas, c'est de la mémoire : la récursion ne descend que d'un disque à la fois, donc elle garde O(n) blocs de pile — un par disque plus un pour le cas de base : seize pour le plus grand plateau ici, soixante-cinq pour la légende. La dérivation complète, et pourquoi ce n'est pas une récurrence à laquelle s'applique le Master Theorem, se trouve sur la page de l'algorithme des Tours de Hanoï.

Coups minimaux selon le nombre de disques

Voici les tailles jouables ici. La catégorie de difficulté est celle que le plateau affiche à côté du sélecteur de disques, et chaque nombre de disques mène à la liste de coups qui le résout.

Au-delà du plateau

Passé 15 disques, le casse-tête cesse d'être quelque chose qui se joue pour devenir quelque chose qui se calcule. Les nombres restent exacts — ils ne sont simplement plus atteignables dans une vie humaine.

Ces nombres ont un nom

Un nombre situé juste en dessous d'une puissance de deux est un nombre de Mersenne, noté M_n = 2ⁿ − 1 — donc chaque valeur des tableaux ci-dessus en est un, et le nombre de coups d'une partie des Tours de Hanoï n'est jamais autre chose. Quand un nombre de Mersenne se trouve être premier, c'est un nombre premier de Mersenne, et ce sont ces nombres que la chasse aux records de primalité poursuit depuis des décennies, parce que 2ⁿ − 1 est bien moins coûteux à tester qu'un nombre quelconque de la même taille.

M_n ne peut être premier que si n l'est aussi, mais cela ne suffit pas — et le contre-exemple est une partie jouable ici. Onze est premier ; ses 2 047 coups ne le sont pas, puisque 2 047 = 23 × 89. Parmi les tailles de ce plateau, celles dont le nombre de coups est premier sont 3, 5, 7 et 13 disques. OEIS A000225 donne la suite complète.

La légende des soixante-quatre disques

Le casse-tête est mis en vente en 1883 et, en moins d'un an, il a son histoire : dans un temple de Bénarès, des prêtres déplacent soixante-quatre disques d'or entre trois aiguilles de diamant, et quand le dernier disque sera posé, le monde prendra fin. L'arithmétique rassure. Soixante-quatre disques demandent 18 446 744 073 709 551 615 coups, et à un coup par seconde cela fait 585 milliards d'années — environ quarante fois l'âge actuel de l'univers.

Questions fréquentes

Combien de coups faut-il aux Tours de Hanoï ?

Le minimum est de 2ⁿ − 1 coups pour n disques. Trois disques en demandent 7, cinq en demandent 31, dix en demandent 1 023 et vingt en demandent 1 048 575. Chaque disque supplémentaire fait un peu plus que doubler le total, car résoudre n disques revient à résoudre n − 1 disques deux fois avec un coup entre les deux.

Pourquoi la formule est-elle 2ⁿ − 1 ?

Pour déplacer n disques, il faut d'abord écarter les n − 1 du dessus, puis déplacer une fois le plus grand disque, puis ramener ces n − 1 par-dessus. Cela donne T(n) = 2·T(n−1) + 1 avec T(1) = 1, et en déroulant on obtient 1, 3, 7, 15, 31 — chacun le double du précédent plus un, soit exactement 2ⁿ − 1.

Quelle est la complexité en temps des Tours de Hanoï ?

O(2ⁿ). Chaque disque double le travail, donc la solution récursive fait 2ⁿ − 1 coups, et aucun algorithme ne peut faire mieux : les coups eux-mêmes doivent être produits, et il y en a autant. L'espace n'est que O(n) : la récursion descend d'un disque à la fois, donc elle garde au plus n + 1 blocs de pile à la fois — c'est pourquoi un appel à 64 disques épuiserait votre patience bien avant la pile.

Combien de temps prendraient 64 disques ?

Soixante-quatre disques demandent 18 446 744 073 709 551 615 coups. À un coup par seconde, cela fait 585 milliards d'années — bien plus que l'âge actuel de l'univers, ce qui est tout le propos de la légende attachée au casse-tête en 1884.

Une solution peut-elle être plus courte que 2ⁿ − 1 ?

Non. 2ⁿ − 1 est une borne inférieure démontrée, pas un simple record : le plus grand disque doit bouger au moins une fois, et avant qu'il le puisse, tous les disques plus petits ne doivent être ni sur lui ni sur sa destination. Cela impose les deux sous-transferts, et l'argument se répète jusqu'en bas.

La calculatrice fonctionne-t-elle sur un plateau à moitié résolu ?

Pas cette page : 2ⁿ − 1 suppose que tous les disques partent d'une même tour. Pour la solution la plus courte depuis une position déjà entamée, utilisez le solveur, qui calcule le chemin optimal depuis n'importe quelle disposition légale. Ouvrir le solveur →