Tours de Hanoï

Jouer aux Tours de Hanoï en ligne

Le plateau en haut de cette page est un jeu gratuit des Tours de Hanoï qui tourne dans votre navigateur : rien à télécharger, aucun compte à créer. Choisissez de 3 à 15 disques, puis déplacez toute la pile de la tour de gauche vers celle de droite.

• Téléphone ou tablette : touchez une tour pour soulever son disque du dessus, puis une autre pour le poser.
• Souris : faites glisser un disque, ou cliquez sur une tour puis sur une autre.
• Clavier : ← et → choisissent une tour, ↑ soulève et ↓ pose ; 1, 2 et 3 vont directement aux tours A, B et C, et Échap repose le disque.

Les erreurs ne coûtent rien. Annuler reprend votre dernier coup, Réinitialiser relance la même taille, et Indice soulève le disque que jouerait la solution la plus courte en disant où il va. Un coup le joue pour vous. Et si vous préférez regarder, Résoudre termine le casse-tête depuis l'endroit où en est le plateau, et pas seulement depuis le début.

Rien n'est compté tant que vous n'avez pas joué. Après votre premier coup, le panneau affiche :

• vos coups, un chronomètre et un score d'efficacité — votre partie en pourcentage d'une partie parfaite ;
• si vous êtes toujours sur le chemin optimal, ou de combien de coups vous vous en êtes écarté.

La chronologie sous le plateau enregistre toute la partie. Revenez à n'importe quelle position, ou rejouez-la à 0,5×, 1×, 2× ou 4× ; la même vitesse règle le rythme de Résoudre. Le mode concentration ne laisse que les tours à l'écran, et la page se souvient du nombre de disques de votre dernière partie. À la fin, l'écran de résultat compare vos coups au minimum et vous propose un disque de plus.

Le problème des Tours de Hanoï

Le problème commence avec trois tours et une pile de disques de tailles différentes posée sur l'une d'elles, le plus grand en bas. Le but est de déplacer toute la pile sur une autre tour, sous trois règles :

1. On déplace un seul disque à la fois.
2. Seul le disque du dessus d'une tour peut bouger.
3. Un disque plus grand ne peut jamais reposer sur un plus petit.

C'est tout le casse-tête, et cela s'apprend en une minute. La troisième règle est ce qui le rend difficile : chaque disque doit attendre quelque part de légal pendant que ceux du dessous se déplacent, et avec seulement trois tours la place manque toujours. Comment jouer aux Tours de Hanoï les montre en images, avec un plateau d'entraînement et un exemple détaillé.

Le mathématicien français Édouard Lucas a publié le casse-tête en 1883. Un an plus tard, un article de revue qui le présentait y a ajouté la légende qui l'a rendu célèbre : des prêtres brahmanes déplaçant soixante-quatre disques d'or, et la fin du monde à leur dernier coup. À un coup par seconde, cela prendrait environ 585 milliards d'années.

Coups minimum et la formule 2ⁿ − 1

Le nombre minimal de coups pour des Tours de Hanoï à n disques est 2ⁿ − 1, souvent écrit 2^n − 1. Trois disques demandent 7 coups, quatre en demandent 15, et les Tours de Hanoï à 5 disques demandent au minimum 31 coups. C'est un plancher démontré et non un record : aucune solution plus courte n'existe, pour aucune taille, et c'est le nombre auquel le score d'efficacité du plateau vous compare.

L'équation derrière la formule

L'équation découle directement des règles. Avant que le plus grand disque puisse bouger, les n − 1 disques au-dessus de lui doivent être empilés sur la tour libre ; ensuite il traverse ; ensuite ces disques reviennent par-dessus. En notant T(n) le plus petit nombre de coups qui fait tout cela :

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

Chaque taille coûte le double de celle du dessous, plus un : 1, 3, 7, 15, 31, 63. Chacun de ces nombres vaut une puissance de deux moins un, d'où la forme close T(n) = 2ⁿ − 1. La démonstration que 2ⁿ − 1 est bien le minimum traite les deux moitiés de l'affirmation — pourquoi ce nombre de coups suffit toujours, et pourquoi moins est impossible — et la calculatrice du nombre minimal de coups donne le compte exact pour n'importe quel nombre de disques jusqu'à soixante-quatre.

Coups minimum selon le nombre de disques

Chaque taille renvoie à sa solution complète, tous les coups listés et joués sur un plateau. La plus grande partie ici compte 15 disques, soit 32 767 coups : chaque disque ajouté double la longueur de la partie, plus un coup.

L'algorithme des Tours de Hanoï et la récursivité

L'équation ci-dessus est aussi l'algorithme, lue comme une suite d'instructions. Pour déplacer n disques d'une tour de départ vers une tour d'arrivée :

1. Déplacez n − 1 disques du départ vers la tour libre.
2. Déplacez le plus grand disque du départ vers l'arrivée.
3. Déplacez les n − 1 disques de la tour libre vers l'arrivée.

Les étapes 1 et 3 sont le même problème avec un disque de moins : l'algorithme les résout donc en s'appelant lui-même, et un appel sans disque à déplacer se contente de rendre la main. Voilà toute la récursivité des Tours de Hanoï, et c'est pourquoi presque tous les cours d'informatique s'en servent pour enseigner la récursivité. L'astuce est de ne pas essayer de se représenter tous les coups d'un coup : faites confiance au plus petit appel pour faire son travail, et les trois étapes sont la solution entière.

Comme l'algorithme joue exactement 2ⁿ − 1 coups, son temps d'exécution est en O(2ⁿ), et rien ne peut faire mieux : chacun de ces coups doit être joué. Sa consommation mémoire, elle, n'est que de O(n). La page de l'algorithme des Tours de Hanoï exécute le code ligne par ligne à côté d'un plateau vivant et dessine l'arbre des appels au fur et à mesure, et la solution itérative produit les mêmes coups avec deux règles et une boucle.

Tours de Hanoï en Python, Java et autres langages

Les trois étapes se traduisent presque mot pour mot en code. Les Tours de Hanoï en Python tiennent dans une fonction de sept lignes : un cas de base pour zéro disque, deux appels récursifs, et la ligne entre les deux qui affiche un coup. Les Tours de Hanoï en Java, c'est la même méthode dans une classe, et l'endroit où découvrir pourquoi le compte pour soixante-quatre disques ne tient pas dans un long. Il y a aussi des programmes complets en C, C++, C# et JavaScript.

Chaque listing a été exécuté et sa sortie vérifiée contre le solveur de ce site, et chacun s'accompagne d'une explication qui dit pourquoi chaque ligne est là, et non ce que fait la syntaxe.

D'autres façons de jouer et d'apprendre

Une fois que trois tours et une pile complète vous semblent faciles, il y a plus à essayer :

• Le défi du jour — une position mélangée, la même pour tout le monde, nouvelle à minuit UTC. Résolvez-la sans le solveur pour entretenir votre série.
• Le solveur — chaque coup de la solution la plus courte depuis n'importe quelle position légale, y compris celle où vous êtes bloqué sur ce plateau.
• Stratégies — l'idée unique qui se répète derrière chaque taille, et une règle qui donne le coup suivant sans rien anticiper.
• Variantes — quatre tours au lieu de trois, un anneau où les disques ne circulent que dans un sens, deux couleurs à trier et un départ aléatoire.
• Pour les enseignants — une séance de 45 minutes, une fiche imprimable avec les corrigés, et un plateau à intégrer dans une page de cours.

Questions fréquentes

Que sont les Tours de Hanoï ?

Les Tours de Hanoï sont un casse-tête à trois tours et une pile de disques de tailles différentes. Il faut déplacer toute la pile d'une tour vers une autre, un disque à la fois, sans jamais poser un disque plus grand sur un plus petit. Le mathématicien français Édouard Lucas l'a publié en 1883.

Puis-je jouer gratuitement aux Tours de Hanoï en ligne ?

Oui. Le plateau de cette page est gratuit, fonctionne dans tout navigateur moderne sur téléphone, tablette ou ordinateur, et ne demande ni téléchargement ni compte. Le nombre de disques de votre dernière partie et vos meilleurs scores sont enregistrés dans votre propre navigateur, pas sur un serveur.

Quel est le nombre minimal de coups aux Tours de Hanoï ?

Une partie parfaite à n disques compte 2ⁿ − 1 coups. Trois disques en demandent 7, cinq en demandent 31, et 15 disques en demandent 32 767. Aucune solution plus courte n'existe : ce nombre est un plancher, pas seulement un objectif.

Comment résout-on les Tours de Hanoï ?

Toute solution est la même idée répétée : pour amener une pile de n disques à l'arrivée, écartez d'abord les n − 1 disques du dessus sur la tour libre, faites traverser le plus grand disque, puis ramenez ces n − 1 disques par-dessus. La plus petite pile obéit exactement à la même règle, et c'est pourquoi une seule méthode résout toutes les tailles.

Y a-t-il une astuce pour connaître le coup suivant ?

Oui. À chaque coup impair, déplacez le plus petit disque d'une tour dans une direction fixe : vers la gauche si le nombre de disques est impair, vers la droite s'il est pair, en revenant au bout. Avec trois disques, son tout premier coup passe donc de A à C. À chaque coup pair, jouez l'unique coup légal qui ne touche pas au plus petit disque. En alternant les deux, on joue une partie parfaite sans rien planifier.

Avec combien de disques puis-je jouer ici ?

De 3 à 15 disques. Commencez à 3 pour saisir la forme de la solution, puis ajoutez un disque à la fois : chaque disque ajouté double à peu près le travail.

Puis-je annuler un coup ou rejouer ma partie ?

Oui. Il y a un bouton d'annulation, et chaque partie garde en plus une chronologie complète : revenez à n'importe quelle position et le plateau affiche exactement cet état, ou rejouez votre partie à quatre vitesses pour voir où vous avez quitté le chemin optimal.