Résoudre
Solveur des Tours de Hanoï
La solution la plus courte pour toute position légale, pas seulement pour une pile complète. Reproduisez le plateau tel qu'il est et regardez le chemin optimal se jouer.
Solution optimale
31coups25 − 1 = 31
Le casse-tête classique : tous les disques partent de la tour A et finissent sur la tour C.
Prêt à jouerÉtape 0 sur 31
←→pas à pasEspacelectureDébutFinaux extrémités
Tous les coups, dans l'ordre
Le disque 1 est le plus petit, et A → C signifie : prendre le disque du haut de la tour A et le poser sur la tour C. Sélectionnez une ligne pour amener le plateau à ce coup.
Le coup 16 est le disque 5 qui passe de A à C. Les 15 coups de part et d'autre sont deux fois la même solution : celle à 4 disques, jouée d'abord vers la tour intermédiaire, puis depuis elle.
| # | Disque | De | Vers |
|---|---|---|---|
| 1 | 1 | A | C |
| 2 | 2 | A | B |
| 3 | 1 | C | B |
| 4 | 3 | A | C |
| 5 | 1 | B | A |
| 6 | 2 | B | C |
| 7 | 1 | A | C |
| 8 | 4 | A | B |
| 9 | 1 | C | B |
| 10 | 2 | C | A |
| 11 | 1 | B | A |
| 12 | 3 | C | B |
| 13 | 1 | A | C |
| 14 | 2 | A | B |
| 15 | 1 | C | B |
| 16 | 5 | A | C |
| 17 | 1 | B | A |
| 18 | 2 | B | C |
| 19 | 1 | A | C |
| 20 | 3 | B | A |
| 21 | 1 | C | B |
| 22 | 2 | C | A |
| 23 | 1 | B | A |
| 24 | 4 | B | C |
| 25 | 1 | A | C |
| 26 | 2 | A | B |
| 27 | 1 | C | B |
| 28 | 3 | A | C |
| 29 | 1 | B | A |
| 30 | 2 | B | C |
| 31 | 1 | A | C |
Sur cette page
Comment fonctionne le solveur
La méthode est la logique du casse-tête lui-même, déroulée vers l'avant. Pour poser le plus grand disque sur sa tour d'arrivée, tous les disques plus petits doivent être ailleurs — plus précisément, empilés sur la seule tour restante. Le solveur demande donc d'abord que cette petite pile s'y rende, fait traverser le grand disque, puis demande que la petite pile revienne par-dessus. Chacune de ces demandes est le même problème avec un disque de moins, jusqu'à un disque unique, qui se déplace en une étape.
Ce qui distingue ce solveur de ceux qui ne traitent qu'une pile complète tient en une ligne de raisonnement : si le plus grand disque est déjà sur sa tour d'arrivée, il n'y a rien à faire pour lui, et le problème se réduit aux disques posés dessus. Ce seul cas lui permet de résoudre depuis un plateau à moitié fait au lieu de vous faire tout recommencer — et c'est pourquoi les nombres de coups qu'il annonce depuis une position personnalisée sont inférieurs à 2ⁿ − 1, souvent de beaucoup pour une partie déjà entamée.
Déplacer les n−1 disques du dessus vers la tour intermédiaire. Rien d'autre n'est possible tant qu'ils sont là.
Le plus grand disque est libre, et sa tour d'arrivée est vide. Il passe en un seul coup — le seul dont cette phase a besoin.
Reconstruire la pile de n−1 disques par-dessus. C'est le même problème avec un disque de moins, jusqu'à un disque unique qui se déplace en un coup.
Lire une solution
Chaque ligne nomme un coup : quel disque, quelle tour il quitte, quelle tour il rejoint. Le disque 1 est le plus petit. Vous n'avez jamais à vérifier la légalité : par construction, tous les coups de la liste sont déjà légaux.
Depuis une pile complète, deux motifs sautent aux yeux :
- Le plus petit disque bouge un coup sur deux — les coups 1, 3, 5, et ainsi de suite — et tourne toujours dans le même sens entre les trois tours.
- Chaque coup intermédiaire est le seul coup légal qui ne touche pas au plus petit disque.
C'est toute la méthode itérative, et elle se lit directement sur n'importe quelle solution partie d'une pile complète. Depuis une position personnalisée, la liste reste la plus courte, mais elle est cousue à partir de transferts plus petits : le plus petit disque peut donc changer de sens en cours de route. La solution itérative montre pourquoi la méthode marche, et le guide des stratégies en fait quelque chose à jouer. Pour la récursivité elle-même, suivie ligne à ligne dans six langages, voyez l'algorithme des Tours de Hanoï.
Les tailles courantes ont aussi chacune leur page, avec tous les coups et ce qui leur est propre : les solutions de 3 à 10 disques et les 64 disques de la légende.
Emporter une solution
La barre d'adresse décrit toujours le plateau à l'écran. Un transfert complet se lit ?disks=5&from=A&to=C ; une position personnalisée y ajoute un code comme pos=CBBAA, une lettre par disque en commençant par le plus petit. Copiez ce lien et il rouvrira exactement ce casse-tête — c'est aussi ainsi que l'on envoie la position où l'on bloque plutôt qu'une description de celle-ci.
La liste des coups se copie dans le presse-papiers, ou se télécharge en fichier texte pour la lire à côté d'un vrai casse-tête et en CSV pour l'ouvrir dans un tableur. Le téléchargement n'a pas la limite du tableau imprimé : à quinze disques, le fichier contient toujours les 32 767 coups.
Pourquoi la liste s'arrête à 12 disques
Les solutions doublent à chaque disque. Douze disques font 4 095 coups : un tableau long, mais utilisable. Treize en font 8 191, vingt en font 1 048 575, et aucun navigateur ne transforme un tableau d'un million de lignes en quelque chose d'utilisable. Au-delà de douze disques, cette page donne le nombre exact et garde le plateau animé — et les téléchargements ci-dessus contiennent toujours tous les coups : la solution reste à vous, elle n'est simplement pas imprimée. Pour les nombres seuls, la calculatrice va jusqu'à soixante-quatre disques et au-delà.
Questions fréquentes
Que fait le solveur des Tours de Hanoï ?
Il affiche la plus courte suite de coups possible qui rassemble tous les disques sur une seule tour. Donnez-lui un nombre de disques et il résout le transfert complet classique ; donnez-lui une position à moitié faite et il résout à partir de là, ce que la plupart des solveurs ne savent pas faire.
La solution est-elle la plus courte ?
Oui. Le solveur est non seulement correct mais prouvé optimal : depuis une pile de départ complète il produit exactement 2ⁿ − 1 coups, et depuis toute autre position légale il produit le véritable plus court chemin vers le but. Aucune suite ne comporte moins de coups.
Peut-il résoudre une position déjà commencée ?
Oui — c'est à cela que sert la position de départ personnalisée. Placez chaque disque sur la tour où il se trouve et le solveur terminera le travail en un minimum de coups depuis cette position, généralement bien moins que de tout reprendre.
Puis-je partager ou mettre en favori une solution ?
Oui. La barre d'adresse contient toujours le plateau que vous regardez : /fr/solver/?disks=5&from=A&to=C est un transfert complet de cinq disques, et une position personnalisée y ajoute un code comme pos=CBBAA, une lettre par disque en commençant par le plus petit. Copiez le lien et il rouvre exactement ce casse-tête.
Puis-je télécharger la liste des coups ?
Oui, en fichier .txt ou en .csv avec une ligne par coup, à côté du bouton de copie. Le téléchargement fonctionne même pour les très longues solutions que la page n'imprime pas en tableau : une réponse à 15 disques reste donc à vous.
Comment lire la liste des coups ?
Chaque ligne nomme un coup : le numéro du disque, la tour qu'il quitte et celle où il se pose. Le disque 1 est le plus petit. Jouez-les dans l'ordre et le casse-tête se résout tout seul ; vous n'avez jamais à vous demander quel disque est jouable, car tous les coups listés le sont déjà.
Pourquoi la liste des coups s'arrête-t-elle à 12 disques ?
Une solution à 12 disques fait 4 095 coups. À 20 disques, ce serait 1 048 575 lignes, qu'aucun navigateur n'affiche de façon utile : au-delà de 12 disques, la page donne le nombre exact de coups et la formule à la place de la liste, et le plateau animé joue toujours la solution.