Stratégie de la Tour de Hanoï : la résoudre en 2^n − 1 coups (2026)

Dernière mise à jour : 17 octobre 2026 · Testé sur le build Tower of Hanoi de Playnesta (casse-tête mathématique du domaine public d'Édouard Lucas, 1883 ; le module de règles, la coque, la feuille de style, le pont et le shim tactile sont originaux Playnesta, MIT ; la mise en page de l'interface s'inspire d'AJLoveChina/Hanoi @ 917b8d6, MIT, référence de mécanisme uniquement) · 3 piquets · 3 à 8 disques, 4 par défaut · optimum 2^n − 1 coups (3 disques → 7, 4 → 15, 5 → 31, 6 → 63, 7 → 127, 8 → 255)

Méthode : chaque nombre ci-dessous est une constante du module de règles livré js/hanoi.js (original Playnesta, MIT), lue et vérifiée cette session, pas citée d'un tiers. Le casse-tête est entièrement déterministe, donc ?disks=5 reproduit la même position initiale pour tout le monde, et il n'y a pas de build amont à observer. Constantes vérifiées : 3 piquets (le piquet 0 commence avec tous les disques, le plus grand en bas et le plus petit en haut ; les piquets 1 et 2 commencent vides) ; nombre de disques 3 à 8, par défaut 4 ; l'optimum est 2^n − 1 coups ; un coup est légal seulement si le piquet destination est vide ou si son disque du haut est plus grand que celui qu'on déplace, et un coup illégal (plus grand disque sur un plus petit) est refusé sur le champ et ne change rien ; la victoire ne se déclenche que lorsqu'une tour complète atterrit sur un piquet autre que celui de départ ; Annuler recule d'un coup et efface l'état de victoire ; le compteur de coups se mesure à l'optimum et passe à Parfait ! quand on résout au minimum. Commandes : glisser un disque sur un autre piquet, ou toucher un piquet pour soulever son disque du haut puis toucher un autre pour le déposer ; le menu du nombre de disques (3 à 8), les boutons Annuler, Règles et Nouvelle partie ; une bannière « Résolu ! » avec « Rejouer » à la fin. Pas de minuteur, donc jouez à votre rythme. Ce qui suit est de la stratégie — la page de jeu explique déjà comment manier le plateau ; ici on voit comment le résoudre en un minimum de coups.

1. Tout le jeu tient en un nombre : 2^n − 1

Pour n disques le minimum de coups possible est 2^n − 1, et ce build l'affiche et vous note contre lui. Trois disques demandent 7, quatre 15, cinq 31, six 63, sept 127, huit 255. Ce n'est pas un objectif arbitraire — c'est le plancher mathématique, et aucun humain ne peut faire mieux.

La plupart de ceux qui « résolvent » la Tour de Hanoï le font en deux ou trois fois l'optimum, parce qu'ils déplacent les disques de façon opportuniste et ne remarquent les coups gaspillés qu'à la fin. Le compteur et la bannière Parfait ! de ce build rendent cette perte visible : elle ne passe à Parfait que quand votre nombre de coups égale 2^n − 1 à la victoire. Tant que vous n'avez pas vu cette bannière, vous n'avez pas résolu le casse-tête — vous l'avez seulement terminé. Le premier objectif n'est donc pas « déplacer la tour », mais « déplacer la tour en 2^n − 1 coups », et tout ce qui suit est le chemin.

2. La recette récursive qui touche le plancher

La solution optimale a une forme récursive, et une fois qu'on la voit le casse-tête cesse d'être une recherche pour devenir une liste de vérification. Pour déplacer une tour de n disques du piquet A au piquet C, en utilisant le piquet B comme réserve :

Déplacer les n − 1 disques du haut de A vers B (en utilisant C comme réserve).
Déplacer le plus grand disque de A vers C.
Déplacer la tour de n − 1 de B vers C (en utilisant A comme réserve).

C'est tout l'algorithme. L'étape 2 est le seul déplacement du plus grand disque ; les étapes 1 et 3 sont le même problème d'une taille plus petite. Comme le plus grand disque ne peut se déplacer que lorsqu'il n'y a plus rien dessus et que la destination est vide, on est obligé de le libérer d'abord — et le libérer, c'est résoudre la tour plus petite, qui doit à son tour libérer son plus grand disque, et ainsi de suite jusqu'à un seul disque.

La conséquence pratique : le plus grand disque se déplace exactement une fois, et seulement au milieu de la solution. Si votre plus grand disque s'est déplacé plus d'une fois, vous n'êtes pas sur le chemin optimal — vous l'avez ré-enterré et devrez le libérer de nouveau. Surveillez cela : une session où le disque du bas se fait soulever sans cesse est une session qui finira bien au-delà de 2^n − 1.

3. Les trois erreurs qui coûtent des coups

Déplacer le plus grand disque trop tôt. On ne peut pas le déplacer tant qu'il reste quelque chose sur son piquet, donc chaque coup fait avant que la tour de n − 1 soit complètement garée sur le piquet de réserve est un coup qui retarde le seul coup qui compte. Les débutants brassent souvent les disques du haut « pour commencer » et ne remarquent qu'ensuite que le disque du bas est encore cloué.

Traiter le piquet vide comme une décoration. Le piquet vide n'est pas une réserve qu'on utilise de temps en temps — c'est le terrain de montage qui rend la récursion possible. Dans un jeu à trois piquets, à tout moment un piquet porte la tour qu'on construit, un autre la tour qu'on démonte, et le troisième est libre. Si on n'utilise pas consciemment ces trois rôles, on fait du travail supplémentaire pour contourner celui qu'on a ignoré.

Jouer avec avidité. Le coup légal qui semble le meilleur maintenant est rarement celui que la récursion veut ensuite. « Déplacer le plus petit disque » paraît productif parce qu'il est toujours légal, mais la séquence optimale alterne petits et grands disques selon un motif fixe (pour un nombre impair de disques le plus petit disque cycle A → C → B → A ; pour un nombre pair, A → B → C → A). Si on arrête de penser et qu'on déplace toujours le plus petit disque légal, on termine — mais pas en 2^n − 1.

4. Monter l'échelle des disques, et savoir quand s'arrêter

La difficulté n'est pas linéaire, elle est exponentielle, et les nombres de coups le disent honnêtement :

3 disques / 7 coups — apprenez la récursion ici. Vous pouvez tenir toute la solution en tête.
4 disques / 15 coups — la première taille où il faut faire confiance à la recette plutôt qu'improviser.
5 disques / 31 coups — un vrai casse-tête ; une erreur et vous dépassez de 10.
6 disques / 63 coups — une séance ; prévoyez de finir d'une traite ou vous perdrez le fil.
7 disques / 127 coups — un projet ; utilisez Annuler à bon escient.
8 disques / 255 coups — un marathon ; le jeu le permet, mais la plupart des sessions devraient vivre entre 4 et 6.

Le chemin d'entraînement honnête est 3 → 4 → 5, et seulement ensuite 6. Sauter à 8 « pour voir le grand » n'apprend rien, car 255 coups d'improvisation, c'est de la fatigue, pas de la pratique. Le menu du nombre de disques (3 à 8) et le paramètre ?disks=n de l'URL vous laissent fixer une taille, donc fixez une taille pour une semaine et poursuivez la bannière Parfait ! dessus avant de monter.

5. Utiliser Annuler comme professeur, pas comme béquille

Annuler recule d'un coup et efface l'état de victoire, donc c'est le moyen le plus propre d'apprendre la récursion : jouez jusqu'à douter, revenez à la dernière position que vous aviez comprise, et dérivez le coup suivant de la recette au lieu de deviner. Comme le jeu n'a pas de minuteur, il n'y a aucune pénalité à s'arrêter pour réfléchir — la seule chose mesurée est le nombre de coups.

Deux habitudes qui aident : rejouez le même seed avec ?disks=4 (ou autre) jusqu'à toucher Parfait ! deux fois de suite, et dites à voix haute quel disque vous allez déplacer et pourquoi avant de le déplacer. Si vous ne pouvez pas dire quel disque et pourquoi, vous devinez, et deviner, c'est ce qui pousse le compteur au-dessus de 2^n − 1. Le jeu redistribue aussi la même tour pour une même valeur de ?disks=, vous pouvez donc forcer une position au lieu de repartir d'une nouvelle position aléatoire à chaque fois.

FAQ

En quoi cela diffère-t-il des règles de la page de jeu ?

La page de jeu explique comment le plateau fonctionne — trois piquets, disque du haut seulement, le plus grand ne couvre jamais le plus petit, glisser ou toucher, le compteur contre l'optimum, Annuler, 3 à 8 disques, pas de minuteur. Ce guide tient cela pour acquis et joue la couche au-dessus : le plancher 2^n − 1, la recette récursive, les trois erreurs, l'échelle des disques et comment s'entraîner. Lisez d'abord les règles, puis poursuivez la bannière Parfait !.

2^n − 1 est-il vraiment le minimum possible ?

Oui. Le plus grand disque doit se déplacer au moins une fois, et pour le déplacer les n − 1 disques au-dessus doivent être hors de son piquet et hors du chemin ; par induction cela demande au moins 2^(n−1) − 1 coups avant et 2^(n−1) − 1 après, plus le seul coup du plus grand disque. Trois piquets sont le minimum qui rend le problème non trivial, et avec trois piquets le plancher est exactement 2^n − 1. Les variantes à quatre piquets (le casse-tête de Reve) ont un plancher plus bas, mais ce jeu utilise trois piquets.

Pourquoi la bannière dit « Parfait ! » seulement parfois ?

Parce que « Parfait ! » est réservé à une résolution en exactement 2^n − 1 coups. Résoudre en plus de coups gagne quand même — la bannière « Résolu ! » se déclenche et le nombre de coups s'affiche contre l'optimum — mais Parfait ne s'active que quand votre nombre égale le plancher. Si vous ne l'avez jamais vu, votre nombre de coups est au-dessus du plancher ; le compteur vous dit de combien.

Toute position est-elle soluble ?

Oui. La position initiale est toujours une tour complète sur un piquet, et la recette la résout pour tout n de 3 à 8. Il n'y a pas de mélange ni d'impasse — un coup illégal est simplement refusé et ne change rien, donc on ne peut pas se peindre dans un coin. On peut toujours annuler jusqu'à un état bon connu.

Sur quel nombre de disques m'entraîner ?

Commencez à 3 jusqu'à toucher Parfait ! deux fois de suite, puis 4, puis 5. La plupart des joueurs plafonnent à 5 disques (31 coups), et c'est un bon endroit où rester — 6 et plus sont pour quand on veut une session plus longue, pas pour apprendre. Évitez le 8 pour l'entraînement ; 255 coups d'improvisation, c'est de la fatigue, pas de la pratique.

Où puis-je y jouer ?

Juste sur la page tower-of-hanoi de ce site. Le casse-tête est un problème mathématique du domaine public publié par Édouard Lucas en 1883, donc il n'y a pas de fichiers amont réutilisés octet par octet ; le module de règles, la coque de page, la feuille de style, le pont d'analytique et le shim tactile sont tous originaux Playnesta et MIT. La mise en page de l'interface s'inspire d'AJLoveChina/Hanoi @ 917b8d6 (MIT), qui n'a été lu que comme référence de mécanisme et n'est pas redistribué ici. Playnesta Games est le développeur et l'éditeur de cette implémentation web concrète.