L'algorithme des Tours de Hanoï

procedure hanoi(n, source, target, spare)
    if n == 0 then
        return
    hanoi(n - 1, source, spare, target)
    move disk n from source to target
    hanoi(n - 1, spare, target, source)
end procedure

Ce qu'il faut observer

• Les rôles tournent. La tour B est l'intermédiaire du premier appel et l'arrivée de celui qu'il lance. Chaque niveau de récursivité réétiquette les trois tours, et ce réétiquetage est toute l'astuce.
• La pile ne devient jamais profonde. Trois disques n'ont jamais plus de 4 appels en cours en même temps — un par nombre de disques, de 3 à 0 — alors que le programme fait 15 appels en tout.
• La moitié des appels ne font rien. Sur ces 15 appels, 8 portent sur zéro disque et reviennent aussitôt. C'est le prix du cas de base le plus simple possible.
• La ligne qui déplace s'exécute exactement 2ⁿ − 1 fois. Sept fois, pour trois disques, au fil des 43 étapes de l'exécution.

Le premier point est le plus difficile à saisir pendant que le programme tourne, parce que rien ne bouge sur le plateau quand cela se produit : seuls changent les noms sous les tours. Le voici figé : le premier appel, les deux qui mènent au coup 1, et l'appel qui ramène la pile.

1. hanoi(3, A, C, B)

   Le premier appel : déplacer les 3 disques de A vers C. Cela laisse B comme intermédiaire. Départ A, arrivée C, intermédiaire B.

2. hanoi(2, A, B, C)

   Son premier appel. Le disque 3 ne peut pas bouger avec les disques 1 et 2 dessus, et ceux-ci ne peuvent pas aller sur C, où se rend le disque 3. Donc B, l'intermédiaire d'il y a un instant, devient l'arrivée, et C devient l'intermédiaire. Départ A, arrivée B, intermédiaire C.

3. hanoi(1, A, C, B)

   Un niveau plus bas, le même échange recommence. Pour dégager le disque 2, le disque 1 va sur C, et B redevient l'intermédiaire. Départ A, arrivée C, intermédiaire B.

4. hanoi(2, B, C, A)

   Le disque 3 a traversé. Le second appel de la racine ramène les disques 1 et 2 depuis B par-dessus lui : B est donc maintenant le départ, et A, où tous les disques ont commencé, est l'intermédiaire. Départ B, arrivée C, intermédiaire A.

Le deuxième est plus facile à mettre en doute qu'à vérifier ; voici donc toute l'exécution avec la hauteur de la pile à chacune de ses étapes :

• L'exécution prend 43 étapes et fait 15 appels en tout.
• Le nombre d'appels sur la pile monte et descend entre 0 et 4, et atteint 4 à 8 de ces étapes — chaque fois qu'un appel sans disque à déplacer commence et revient.
• La profondeur 4 est n + 1 pour n = 3, et aucune étape de l'exécution ne la dépasse.

L'arbre de récursion

Dessinez chaque appel comme une case sous l'appel qui l'a lancé et le programme devient un arbre. Placez chaque case au-dessus du numéro du coup qu'elle joue, et autre chose apparaît : lire les cases de gauche à droite donne les coups dans l'ordre. Avec trois disques, le coup propre au premier appel — le plus grand disque — est le coup 4, pile au milieu, avec de part et d'autre la solution complète à deux disques en trois coups.

1. Coup 1 : l'appel avec n = 1, de A vers C, déplace le disque 1.
2. Coup 2 : l'appel avec n = 2, de A vers B, déplace le disque 2, entre ses deux appels avec n = 1.
3. Coup 3 : l'appel avec n = 1, de C vers B, déplace le disque 1.
4. Coup 4 : l'appel avec n = 3, de A vers C, déplace le disque 3, entre ses deux appels avec n = 2.
5. Coup 5 : l'appel avec n = 1, de B vers A, déplace le disque 1.
6. Coup 6 : l'appel avec n = 2, de B vers C, déplace le disque 2, entre ses deux appels avec n = 1.
7. Coup 7 : l'appel avec n = 1, de A vers C, déplace le disque 1.

Cette symétrie tient à toutes les tailles. Le coup 2ⁿ⁻¹ est toujours le plus grand disque qui traverse, et les coups avant et après sont la solution à (n − 1) disques jouée deux fois, avec deux tours qui échangent leurs rôles. C'est pourquoi une liste de coups de n'importe quelle longueur se lit d'un coup d'œil, et pourquoi la solution à cinq disques est celle à quatre, un coup, puis celle à quatre de nouveau.

Pourquoi c'est correct

L'algorithme n'enfreint jamais une règle et se termine toujours, et la démonstration est assez courte pour être donnée en entier. L'affirmation, pour tout n, est :

Si les n disques du dessus de la tour de départ sont les disques 1 à n, et que tout disque situé ailleurs est plus grand que n, alors hanoi(n, source, target, spare) déplace ces n disques vers l'arrivée, légalement, et ne touche à rien d'autre.

Pour n = 0, il n'y a rien à déplacer et rien n'est touché.

Supposons l'affirmation vraie pour n − 1. Alors chacune des trois étapes est légale :

1. Le premier appel déplace les disques 1 à n − 1 sur l'intermédiaire. Il en a le droit : tous les autres disques, disque n compris, sont plus grands que n − 1.
2. Le disque n va sur l'arrivée. Rien ne le recouvre désormais, et l'arrivée ne contient que des disques plus grands que n.
3. Le second appel déplace les disques 1 à n − 1 de l'intermédiaire vers l'arrivée. Avec le même droit : le disque n, désormais sous eux, est plus grand.

Les n disques sont sur l'arrivée et rien d'autre n'a bougé. Par récurrence, l'affirmation vaut pour tout n, et le casse-tête complet est le cas où la tour de départ porte tous les disques.

1. Supposél'affirmation pour n − 1

   L'hypothèse dit qu'un appel sur n − 1 disques les déplace là où on le lui demande, légalement, et ne touche à rien d'autre. Appliquée ici, elle emporte les disques 1 à n − 1 du départ vers l'intermédiaire. Elle en a le droit : tout disque sur lequel elle pourrait les poser — disque n compris — est plus grand que n'importe lequel de ceux qu'elle porte.

2. Démontré iciun coup légal

   C'est la seule étape que la démonstration doit défendre elle-même, et c'est un seul coup. Le disque n est dégagé, puisque l'étape précédente l'a dégagé. L'arrivée ne contient que des disques plus grands que n, puisque tout ce qui est plus petit est sur l'intermédiaire. Le coup est donc légal.

3. Supposél'affirmation pour n − 1, de nouveau

   La même hypothèse, utilisée une seconde fois, ramène les disques 1 à n − 1 de l'intermédiaire vers l'arrivée. Légal pour la même raison qu'avant : le disque n, maintenant sous eux, est plus grand. Les n disques sont sur l'arrivée et rien d'autre n'a bougé — ce qui est l'affirmation pour n.

La récurrence, résolue correctement

Soit T(n) le nombre de coups que l'algorithme joue pour n disques. La fonction lance deux appels sur n − 1 disques et joue un coup elle-même, et ne joue aucun coup quand il n'y a pas de disque :

Pour la résoudre, substituez la récurrence dans elle-même et cherchez le motif. Cela s'appelle dérouler, ou télescoper :

Repérer un motif n'est pas le démontrer : confirmez-le par récurrence. T(0) = 0 = 2⁰ − 1. Et si T(n − 1) = 2ⁿ⁻¹ − 1, alors T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 2 + 1 = 2ⁿ − 1. La forme close est exacte pour tout n.

Il existe une troisième voie, et c'est une image que vous avez déjà vue. L'arbre de récursion ci-dessus est un arbre binaire complet : la racine déplace n disques, les deux appels en dessous en déplacent n − 1 chacun, les quatre encore en dessous n − 2, et ainsi de suite. La profondeur k contient donc 2ᵏ appels, le dernier niveau est la profondeur n − 1, et chacun de ces appels joue exactement un coup. Additionnez les niveaux et le compte tombe comme une série géométrique :

Trois méthodes — dérouler, le raisonnement par récurrence et l'arbre — et une seule réponse. Bon à savoir, car il en existe une quatrième, proposée sans arrêt, et elle est fausse.

La même arithmétique compte les appels. Chaque appel avec n {">"} 0 disques en lance deux autres, il y a donc C(n) = 2C(n − 1) + 1 appels avec C(0) = 1, ce qui se déroule en 2ⁿ⁺¹ − 1. Soit 2ⁿ − 1 appels qui déplacent un disque, plus 2ⁿ qui reviennent immédiatement.

Complexité en temps et en mémoire

Chaque appel fait une quantité constante de travail en plus de ses deux appels récursifs : le temps d'exécution est donc proportionnel au nombre d'appels, soit Θ(2ⁿ). Aucun algorithme plus malin ne peut faire mieux, parce que la sortie elle-même fait 2ⁿ − 1 coups — et 2ⁿ − 1 est un minimum démontré, pas seulement le meilleur résultat connu. La démonstration qu'aucune solution n'est plus courte a sa propre page : pourquoi le minimum est 2ⁿ − 1.

La mémoire, c'est une autre histoire. Les appels n'existent pas tous en même temps : un appel se termine avant que son frère ne commence, donc la pile ne garde qu'un appel par niveau, de n jusqu'à 0. L'espace utilisé est Θ(n) — soixante-cinq blocs de pile pour les soixante-quatre disques de la légende, ce que n'importe quel ordinateur encaisse sans sourciller. C'est le temps qui manque : 18 446 744 073 709 551 615 coups à un milliard par seconde font encore 584 ans.

Ce nombre est celui de la légende, et la légende est plus jeune qu'elle n'en a l'air. Un temple où des prêtres déplacent soixante-quatre disques d'or, et la fin du monde quand ils auront fini, apparaît pour la première fois imprimé en 1884 — dans un article vantant un casse-tête mis en vente à Paris l'année précédente, sous le nom d'un professeur qui n'existait pas. Au rythme des moines, un coup par seconde, il reste 585 milliards d'années au monde, soit environ quarante fois l'âge actuel de l'univers. Le mathématicien derrière le casse-tête et l'histoire était Édouard Lucas, qui démontra à la main que 2¹²⁷ − 1 est premier, puis mourut à 49 ans d'une infection due à une coupure faite par une assiette qu'un serveur avait laissée tomber lors d'un banquet.

Mettez des nombres dans ces formules et les deux sortes de coût se séparent. Chaque disque supplémentaire fait un peu plus que doubler les coups et les appels, et ajoute un seul bloc à la profondeur maximale de la pile :

La calculatrice des coups minimaux donne les coups et le temps pour n'importe quel nombre de disques, et la dernière ligne — la taille de la légende — a sa propre page.

Sans récursivité

Les mêmes coups peuvent être produits par une simple boucle avec deux règles :

• Coups impairs : le plus petit disque avance d'une tour sur un circuit fixe — A → C → B pour un nombre impair de disques, A → B → C pour un nombre pair.
• Coups pairs : jouez le seul coup légal qui ne touche pas au plus petit disque. Il y en a toujours exactement un.

Ces deux règles reproduisent la solution récursive coup pour coup ; la page de la solution itérative montre pourquoi, et la joue sur un plateau.

Il existe une version plus étrange encore, qui ne stocke aucune tour : le disque, le départ et l'arrivée du coup m se lisent chacun sur les chiffres binaires de m. Ce lien, et le code de Gray qui s'y cache, sont dans Tours de Hanoï, binaire et code de Gray.

Depuis une position qui n'est pas le début

La fonction du manuel suppose que tous les disques partent de la tour de départ. Donnez-lui un casse-tête à moitié fait et elle n'a rien à en dire. Un cas de plus règle cela. Regardez le plus grand disque :

• Déjà sur la tour qu'il doit atteindre ? Il n'a besoin d'aucun coup. Résolvez les disques plus petits en les envoyant sur cette même tour.
• Ailleurs ? Dégagez les disques plus petits vers la tour qui n'est ni celle où il est ni celle où il va, déplacez-le, et continuez comme avant.

Cette version trouve la solution la plus courte depuis n'importe quelle position légale, et c'est elle que fait tourner le solveur des Tours de Hanoï.

Testez-vous

Trois questions auxquelles la page a déjà répondu. Cherchez la réponse avant d'ouvrir — si l'une ne vient pas, la section nommée avec la réponse est celle à relire.

1. Trois disques font sept coups. Combien en font 5 disques, et combien d'entre eux déplacent le disque 5 lui-même ?

   Voir la réponse

   31 coups, soit 2⁵ − 1 — et exactement un d'entre eux déplace le plus grand disque. Tous les disques sauf le plus grand bougent plus d'une fois, parce que chacune des deux moitiés de la solution doit les déplacer. La récurrence, résolue correctement.

2. hanoi(3, A, C, B) lance hanoi(2, A, B, C) comme premier appel. Pourquoi l'arrivée de cet appel est-elle B plutôt que C ?

   Voir la réponse

   Parce que le disque 3 va en C, et qu'il ne peut s'y poser que si C est vide. Les deux disques posés dessus doivent donc être garés ailleurs, et cet ailleurs ne peut être que B. La tour que vise un appel devient celle que son premier appel doit garder libre — c'est pourquoi deux des trois arguments échangent leur place en entrant. Ce qu'il faut observer.

3. Résoudre 20 disques fait 2 097 151 appels. Combien d'entre eux sont sur la pile au même instant, au maximum ?

   Voir la réponse

   21 — un par nombre de disques, de 20 à 0. Un appel se termine avant que son frère ne commence, donc les appels n'existent jamais tous en même temps : le travail est exponentiel et la mémoire est linéaire. Complexité en temps et en mémoire.

L'algorithme dans votre langage

La même fonction dans six langages, chacun avec un programme exécutable, une explication ligne à ligne, le plateau qui tourne à côté, et ce qui est propre à ce langage — ce qui devient important dès qu'on essaie de compter les coups pour soixante-quatre disques. Ces six pages sont en anglais.

• Tours de Hanoï en PythonENRecursive and iterative programs, why Python's recursion limit never bites here, and integers that simply do not overflow.
• Tours de Hanoï en JavaScriptENWhy 2 ** 64 − 1 prints the wrong number, BigInt, and a generator that hands out one move at a time.
• Tours de Hanoï en JavaENWhy (1L << 64) − 1 is zero, counting with BigInteger, and the same solution driven by an explicit stack.
• Tours de Hanoï en CENUndefined shifts, uint64_t, and a loop that reads every move straight off the bits of the move number.
• Tours de Hanoï en C++ENCollecting the moves in a std::vector, the 64-disk count checked by the compiler, and three pairs of towers in a loop.
• Tours de Hanoï en C#ENTop-level statements, an iterator whose moves LINQ can query, and ulong, checked arithmetic and UInt128 for the move count.

Les mots de cette page

Cas de base

La version du problème qu'une fonction récursive traite directement, sans s'appeler elle-même. C'est ce qui arrête la récursivité. Ici c'est n = 0 : aucun disque à déplacer, donc rien à faire, et l'appel revient. Toute chaîne d'appels, si profonde soit-elle, se termine sur l'un d'eux.

Cas récursif

Tout ce qui n'est pas le cas de base : la partie de la fonction qui résout une version plus petite du même problème et construit sa réponse à partir d'elle. Ici, ce sont les trois lignes qui dégagent n − 1 disques, déplacent le disque n, et ramènent ces n − 1 disques.

Pile d'appels

La liste des appels de fonction commencés et pas encore terminés, le plus récent en dernier. Un appel est empilé quand il commence et dépilé quand il revient : la pile est donc la façon dont un programme se souvient d'où revenir. C'est ce que dessine le panneau ci-dessus, et c'est de la vraie mémoire — d'où le fait que sa profondeur soit le coût en espace de l'algorithme.

Bloc de pile

Une entrée de la pile d'appels : les arguments et les variables locales d'un seul appel. Chaque ligne de la pile dans le panneau est un bloc, avec son propre n et sa propre idée de quelle tour est le départ, l'arrivée et l'intermédiaire. Soixante-quatre disques demandent soixante-cinq blocs, ce qui n'est rien ; le problème, ce sont les coups.

Télescoper

Aussi appelé dérouler : résoudre une récurrence en la substituant dans elle-même jusqu'à ce que le motif saute aux yeux, puis en fixant le nombre de substitutions pour qu'il ne reste que la valeur initiale connue. On parle de télescopage parce que les termes du milieu se replient comme les sections d'une longue-vue.

Θsaid “grand thêta”

Un ordre de croissance qui est à la fois une borne supérieure et une borne inférieure : Θ(2ⁿ) veut dire que le coût croît comme 2ⁿ, pas seulement qu'il ne croît pas plus vite. O(2ⁿ) ne promettrait que le plafond. Θ est ici la notation honnête, parce que cet algorithme joue vraiment 2ⁿ − 1 coups — il ne peut pas avoir de la chance et finir plus tôt.

Questions fréquentes

Comment fonctionne l'algorithme récursif des Tours de Hanoï ?

Pour déplacer n disques d'une tour de départ vers une tour d'arrivée, il déplace d'abord les n − 1 disques du dessus sur la tour intermédiaire, puis le plus grand disque vers l'arrivée, puis les n − 1 disques de l'intermédiaire vers l'arrivée. Chacun de ces deux transferts plus petits est le même problème avec un disque de moins, donc la fonction s'appelle elle-même pour eux, et un appel sans disque à déplacer se contente de revenir.

Les Tours de Hanoï, est-ce diviser pour régner ou de la programmation dynamique ?

C'est diviser pour régner. Le problème est divisé en deux sous-problèmes de n − 1 disques, chacun est réglé par récursivité, et l'étape de combinaison est un unique déplacement du plus grand disque. Ce n'est pas de la programmation dynamique, et la mémoïsation n'aide pas — même si les sous-problèmes se répètent réellement. Avec trois tours, il n'y a que six façons de nommer un départ, une arrivée et un intermédiaire, donc hanoi(1, A, C, B) est bel et bien appelé deux fois pendant la résolution à trois disques. Le mettre en cache n'apporte rien, car la réponse à un sous-problème est une liste de 2ᵏ − 1 coups, et rejouer une liste stockée de cette longueur coûte autant que la produire. Ici, le travail, c'est la sortie, et aucune table ne raccourcit la sortie.

Le Master Theorem s'applique-t-il à la récurrence des Tours de Hanoï ?

Non. Le Master Theorem couvre les récurrences de la forme T(n) = aT(n/b) + f(n), où chaque sous-problème est une fraction de l'original. La récurrence des Tours de Hanoï est T(n) = 2T(n − 1) + 1 : le sous-problème est plus petit d'un disque, pas d'un facteur. La dérouler donne directement T(n) = 2ⁿ − 1, et un raisonnement par récurrence le confirme.

Jusqu'où descend la récursivité ?

Avec un cas de base à n = 0, il y a au plus n + 1 appels sur la pile en même temps : un par nombre de disques, de n à 0. Avec un cas de base à n = 1, c'est n. Dans les deux cas la profondeur croît linéairement, et c'est pourquoi la solution récursive n'a besoin que de O(n) de mémoire alors qu'elle joue un nombre exponentiel de coups.

Combien d'appels de fonction la solution récursive fait-elle ?

2ⁿ⁺¹ − 1 appels quand le cas de base est n = 0 : les 2ⁿ − 1 appels qui déplacent un disque, plus 2ⁿ appels qui ne trouvent rien à déplacer et reviennent. Trois disques font 15 appels. Écrit avec un cas de base à n = 1, le même programme fait exactement 2ⁿ − 1 appels, un par coup.

L'algorithme itératif est-il plus rapide que le récursif ?

Pas d'une façon qui compte. Les deux doivent produire 2ⁿ − 1 coups, donc les deux prennent un temps proportionnel à 2ⁿ. La version itérative évite le coût des appels de fonction et ne peut pas épuiser la pile, mais la récursivité ici n'a que n niveaux de profondeur : épuiser la pile n'est pas un risque réel pour un nombre de disques que vous pourriez attendre.

À quoi ressemble l'algorithme des Tours de Hanoï en organigramme ?

À pas grand-chose, et c'est la réponse honnête. Un organigramme montre le contrôle qui traverse des cases une fois, et la deuxième case de cet algorithme est l'organigramme tout entier de nouveau — trois niveaux plus bas, avec deux des tours échangées et un disque de moins. Un organigramme n'a pas de notation pour cela : un organigramme de la solution récursive est donc soit faux, soit l'image d'un seul appel avec deux cases marquées « appeler hanoi », ce qui n'apprend rien de plus que le pseudocode en quatre lignes. Le schéma qui, lui, l'exprime, c'est l'arbre de récursion : chaque appel dessiné sous l'appel qui l'a lancé, chaque case au-dessus du coup qu'elle joue. Il est sur cette page, et lire ses cases de gauche à droite donne les coups dans l'ordre.

L'algorithme peut-il résoudre un casse-tête déjà à moitié fait ?

La version du manuel ne le peut pas : elle suppose que tous les disques partent d'une même tour. Elle se généralise avec un cas de plus — si le plus grand disque est déjà sur son arrivée, passez-le et résolvez les disques du dessus — et cette version trouve la solution la plus courte depuis n'importe quelle position légale. Le solveur de ce site fait tourner exactement cela. Ouvrir le solveur →