Trois piquets, une tour de disques et très peu de règles : les Tours de Hanoï sont un jeu où la planification compte plus que la vitesse. C’est aussi un exemple concret de récursivité : résoudre un problème en utilisant la solution du même problème, mais plus petit.
Ouvrir le laboratoire des Tours de Hanoï : jouer avec 1 à 10 disques
Essayez d’abord avec peu de disques, puis comparez votre parcours à la solution animée.
But et règles du jeu
Les piquets s’appellent A, B et C. Au départ, tous les disques sont sur A, du plus grand en bas au plus petit en haut. Il faut transférer toute la tour sur C ; B sert d’appui temporaire.
- Déplacez un seul disque à la fois.
- Vous ne pouvez prendre que le disque supérieur d’un piquet.
- Ne posez jamais un grand disque sur un plus petit. Un piquet vide peut recevoir n’importe quel disque.
Numérotons les disques du plus petit, 1, au plus grand, n. Dans les exemples, les listes se lisent de bas en haut : [3, 2, 1] représente la tour complète et [] un piquet vide. Un déplacement transfère un disque ; chaque clic de l’interface ne compte pas séparément.
Partons du cas le plus simple
Un disque : un déplacement suffit
Le disque 1 va directement de A vers C. Il n’y a rien à dégager : c’est le plus petit cas non vide du jeu.
Deux disques : libérez d’abord le grand
Le disque 2 ne peut pas bouger immédiatement, car le disque 1 se trouve au-dessus. Voici les trois déplacements nécessaires :
- Disque 1 : A → B.
- Disque 2 : A → C.
- Disque 1 : B → C.
Le piquet auxiliaire n’est pas une destination finale : il permet de dégager le disque à déplacer.
Trois disques : les sept déplacements
Pour libérer le disque 3, transférez d’abord la petite tour [2, 1] de A vers B en utilisant C comme appui. Déplacez ensuite le disque 3 sur C, puis reconstruisez [2, 1] au-dessus. La procédure pour deux disques est identique, mais les piquets changent de rôle.
| Déplacement | Disque | Transfert | A | B | C |
|---|---|---|---|---|---|
| 0 | — | Départ | [3, 2, 1] | [] | [] |
| 1 | 1 | A → C | [3, 2] | [] | [1] |
| 2 | 2 | A → B | [3] | [2] | [1] |
| 3 | 1 | C → B | [3] | [2, 1] | [] |
| 4 | 3 | A → C | [] | [2, 1] | [3] |
| 5 | 1 | B → A | [1] | [2] | [3] |
| 6 | 2 | B → C | [1] | [] | [3, 2] |
| 7 | 1 | A → C | [] | [] | [3, 2, 1] |
La ligne 0 décrit le départ : ce n’est pas un déplacement. De la ligne 1 à la ligne 7, chaque ligne transfère exactement un disque en respectant toutes les règles.
La stratégie générale : un problème dans le problème
Supposons que vous sachiez déjà transférer une tour de n−1 disques. Pour en transférer n de A vers C :
- Déplacez les n−1 disques supérieurs de A vers B en utilisant C comme appui.
- Déplacez le disque n de A vers C.
- Déplacez les n−1 disques de B vers C en utilisant A comme appui.
![Trois positions successives : A=[3], B=[2,1] ; puis B=[2,1], C=[3] ; enfin C=[3,2,1]. Les piquets non indiqués sont vides.](/assets/images/editorial/hanoi-recursion-stages.svg)
« Transférer n−1 disques » ne signifie pas les déplacer en bloc : répétez la même recette avec un disque de moins jusqu’au cas le plus simple. Chaque déplacement effectif concerne toujours un seul disque.
Ce pseudocode précise les rôles des piquets. Avec zéro disque, il n’y a rien à déplacer : cette condition arrête les appels récursifs.
Hanoi(n, départ, arrivée, appui):
si n = 0 : terminer
Hanoi(n−1, départ, appui, arrivée)
déplacer le disque n de départ vers arrivée
Hanoi(n−1, appui, arrivée, départ)L’appel initial est Hanoi(n, A, C, B). Chaque appel change les rôles du départ, de l’arrivée et de l’appui, pas les règles du jeu.
Pourquoi ne peut-on pas faire mieux que 2ⁿ − 1 ?
Notons M(n) le minimum de déplacements pour transférer une tour complète de n disques entre deux piquets. Avant le premier déplacement du plus grand disque, tous les autres doivent être réunis sur le troisième piquet : au moins M(n−1) déplacements sont nécessaires. Le grand disque exige au moins un déplacement. Après sa dernière arrivée sur le piquet final, les petits disques doivent être transférés du troisième piquet au-dessus de lui : au moins M(n−1) déplacements supplémentaires. Les détours ne suppriment pas ces deux transferts obligatoires.
La stratégie décrite réalise exactement ces trois étapes sans déplacement supplémentaire. Elle atteint donc cette borne :
M(0) = 0
M(n) = 2 × M(n−1) + 1 = 2n − 1
Pour vérifier la dernière égalité, remplacez M(n−1) par 2n−1 − 1 : on obtient 2 × (2n−1 − 1) + 1 = 2n − 1. Le cas de base M(0) = 0 complète le raisonnement par récurrence.
| Disques | Minimum de déplacements |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
| 9 | 511 |
| 10 | 1023 |
Un disque de plus double presque le travail. À un déplacement par seconde, 10 disques exigent 1023 secondes, soit 17 minutes et 3 secondes, sans pause. Le nombre de déplacements croît exponentiellement : une règle courte peut décrire une très longue procédure.
Utiliser le laboratoire
Accéder au laboratoire interactif des Tours de Hanoï
- Choisissez de 1 à 10 disques : tous les niveaux sont immédiatement disponibles.
- Touchez le piquet de départ, puis celui d’arrivée. Au clavier, utilisez Tab, Entrée ou Espace.
- « Annuler un déplacement » inverse le dernier transfert ; « Recommencer le niveau » permet de repartir de zéro.
- « Indice » suggère sans déplacer ; « Un pas » effectue un déplacement ; « Lancer la solution » anime le parcours à la vitesse choisie.
- La solution guidée repart de la position actuelle, même après un parcours différent du vôtre. « Pause » laisse terminer le déplacement en cours.
« Minimum depuis le départ » concerne la tour initiale ; « Minimum encore nécessaire » concerne la position actuelle. Après un détour, les déplacements effectués ajoutés à ceux encore nécessaires peuvent dépasser le minimum initial. Les records ne sont actualisés que pour les parties manuelles sans aide et restent dans ce navigateur : ils ne sont pas envoyés au site.
Trois défis avant de révéler les réponses
1. Quel est le minimum de déplacements pour quatre disques ?
Afficher la solution expliquée
Trois disques exigent 7 déplacements. Pour quatre, il en faut 7 pour dégager le disque 4, un pour le déplacer et 7 pour reconstruire la tour : 7 + 1 + 7 = 15. La formule donne également 2⁴ − 1 = 15.
2. Avec trois disques à transférer de A vers C, pourquoi commencer par déplacer le disque 1 de A vers C plutôt que de A vers B ?
Afficher la solution expliquée
Il faut d’abord transférer [2, 1] de A vers B. Pour le faire en trois déplacements, le disque 1 va sur C, le disque 2 sur B, puis le disque 1 sur B. Commencer par A → B est autorisé, mais ne permet pas de terminer toute la tour dans le minimum de 7 déplacements.
3. Vous avez effectué 4 déplacements et le laboratoire en indique encore au moins 5. Pouvez-vous finir en 7 déplacements au total ?
Afficher la solution expliquée
Non : le meilleur total possible depuis cette position est 4 + 5 = 9. La solution guidée optimise le parcours restant, mais n’efface pas les déplacements déjà effectués. Annulez un détour ou recommencez pour tenter le minimum initial.
Que nous apprend ce jeu ?
Les Tours de Hanoï montrent comment décomposer une tâche, reconnaître un sous-problème et fixer une condition d’arrêt. La récursivité ne permet pas de sauter des étapes : elle les organise précisément, en respectant la même contrainte à chaque déplacement.
Référence pour les règles, la stratégie récursive et le minimum de déplacements : NIST — Dictionary of Algorithms and Data Structures: Towers of Hanoi.