Tour de Hanoï : règles, résolution et algorithme expliqués

La tour de Hanoï est l’un des casse-tête les plus célèbres au monde. Trois piquets, une pile de disques, deux règles simples, et pourtant une solution d’une élégance mathématique rare. Voici les règles, la méthode pour la résoudre à coup sûr, la formule du nombre de coups et l’algorithme qui l’a rendue incontournable en informatique.

Jouer à la tour de Hanoï en ligne

Les règles de la tour de Hanoï

Au départ, tous les disques sont empilés sur le piquet de gauche, du plus grand en bas au plus petit en haut. Le but est de déplacer toute la tour sur un autre piquet, en respectant deux règles :

1. On ne déplace qu’un seul disque à la fois : celui du dessus d’une pile.
2. On ne pose jamais un disque sur un disque plus petit.

Nombre minimal de coups : la formule 2ⁿ − 1

Pour n disques, le nombre minimal de coups est 2ⁿ − 1. Chaque disque supplémentaire double donc (plus un) le nombre de coups :

Pourquoi ? Pour déplacer le plus grand disque, il faut d’abord avoir déplacé les n − 1 disques du dessus sur le piquet intermédiaire, puis les remettre dessus. Si T(n) est le nombre de coups, T(n) = 2 × T(n − 1) + 1 avec T(1) = 1, d’où T(n) = 2ⁿ − 1.

Solution pour 3 disques (7 coups)

Piquets A (départ), B (intermédiaire), C (arrivée) ; disques 1 (petit) à 3 (grand) :

1. 1 de A vers C
2. 2 de A vers B
3. 1 de C vers B
4. 3 de A vers C
5. 1 de B vers A
6. 2 de B vers C
7. 1 de A vers C

La méthode infaillible pour n’importe quel nombre de disques

Il existe une règle très simple à retenir, qui fonctionne quel que soit le nombre de disques :

• Coups impairs (1ᵉʳ, 3ᵉ, 5ᵉ…) : déplacez le plus petit disque, toujours dans le même sens de rotation (A → B → C → A…).
• Coups pairs : faites le seul mouvement légal qui ne touche pas au petit disque.

Le sens de rotation dépend de la parité : avec un nombre de disques impair, le petit disque tourne A → C → B → A ; avec un nombre pair, A → B → C → A. Ainsi la tour arrive toujours sur le piquet C, en 2ⁿ − 1 coups exactement.

L’algorithme récursif

La tour de Hanoï est l’exemple classique de récursivité enseigné en informatique :

hanoi(n, depart, arrivee, intermediaire):
    si n = 0 : terminer
    hanoi(n - 1, depart, intermediaire, arrivee)
    déplacer le disque n de depart vers arrivee
    hanoi(n - 1, intermediaire, arrivee, depart)

La version itérative reprend la méthode des coups pairs et impairs décrite plus haut. Autre curiosité : le disque déplacé au coup k est donné par le nombre de zéros à la fin de l’écriture binaire de k (plus un). Cela relie la tour de Hanoï au comptage binaire et au code de Gray.

La légende des 64 disques

Le casse-tête a été publié en 1883 par le mathématicien français Édouard Lucas, sous le pseudonyme de « professeur N. Claus de Siam » (anagramme de Lucas d’Amiens). Il l’accompagnait d’une légende : dans un temple de Bénarès, des moines déplaceraient une tour de 64 disques d’or, et le monde prendrait fin quand ils auraient terminé. Pas d’inquiétude : à un coup par seconde, il leur faudrait environ 585 milliards d’années.

Variantes et utilisations

• Tour de Hanoï à 4 piquets (problème de Reve) : le nombre minimal de coups est donné par l’algorithme de Frame-Stewart, dont l’optimalité n’a été démontrée que récemment.
• Hanoï cyclique : les disques ne peuvent tourner que dans un sens.
• En psychologie : la tour de Hanoï et sa cousine la tour de Londres servent à évaluer la planification et les fonctions exécutives.

Envie de vous entraîner ? Notre tour de Hanoï en ligne propose de 3 à 8 disques, compte vos coups et peut montrer la solution animée.

Questions fréquentes