Tours de Hanoï : questions fréquentes

Il y en a une, et elle est mécanique plutôt qu'astucieuse : à chaque coup impair, déplacez le plus petit disque d'une tour dans la même direction — vers la gauche si le nombre de disques est impair, vers la droite s'il est pair, en revenant au bout, de sorte qu'avec trois disques son tout premier coup passe de A à C. À chaque coup pair, il n'y a jamais qu'un seul coup légal qui ne touche pas au plus petit disque : vous le jouez sans réfléchir. Alternez les deux et vous jouez une partie parfaite sans jamais anticiper le moindre coup. La page des stratégies le détaille.

Commencez avec toute la pile sur la tour de gauche, le plus petit disque au sommet. Le but est la même pile sur la tour de droite. Trois règles : un disque à la fois, toujours le disque du dessus, et jamais un disque plus grand sur un plus petit. Avec trois disques, la partie la plus courte fait sept coups en trois groupes : A→C, A→B, C→B construit les deux plus petits disques sur la tour du milieu ; A→C laisse traverser le plus grand ; et B→A, B→C, A→C reconstruit ces deux-là par-dessus. Comment jouer, avec un plateau d'entraînement.

Facile à apprendre, et difficile d'une seule façon : la partie double de longueur à chaque disque ajouté. Trois disques font sept coups, et la plupart des gens — les enfants dès six ans environ — y arrivent dès le premier essai. Vers cinq ou six disques, l'essai-erreur cesse de fonctionner et il faut une méthode ; et le difficile, dans la méthode, est de faire confiance à des coups qui semblent reculer, comme empiler toute une pile sur la tour du milieu alors que le but est à droite. Une fois l'idée récursive comprise, toutes les tailles sont le même casse-tête. Pourquoi l'idée récursive est tout le casse-tête.

Aucune fédération n'homologue les records de vitesse aux Tours de Hanoï comme il en existe pour le Rubik's cube : les temps annoncés ne sont donc pas comparables, et ils ne précisent généralement pas le nombre de disques, qui est pourtant le seul chiffre qui compte. Calculez plutôt : une partie parfaite à n disques fait 2ⁿ − 1 coups, et un joueur entraîné tient à peu près deux coups par seconde. Cela fait environ quatre secondes pour trois disques, autour de neuf minutes pour dix disques et leurs 1 023 coups, et environ quatre heures et demie pour 15 disques et leurs 32 767. Le plateau de ce site retient votre plus petit nombre de coups pour chaque taille dans votre navigateur, et affiche votre temps sur l'écran de résultat. La calculatrice donne le temps pour toute taille.

2ⁿ − 1, et c'est un plancher démontré, pas un meilleur résultat connu. Trois disques demandent 7 coups, quatre en demandent 15, cinq 31, dix 1 023, et 15 en demandent 32 767. La démonstration a deux moitiés : la méthode récursive atteint ce nombre, et aucune solution ne peut faire mieux, parce que le plus grand disque doit bouger au moins une fois et que tous les disques plus petits au-dessus de lui doivent d'abord être dégagés sur la tour libre puis ramenés ensuite. Les deux moitiés de la démonstration, en entier.

T(n) = 2·T(n − 1) + 1, avec T(0) = 0. Elle se lit directement sur la méthode : pour déplacer n disques, vous écartez n − 1 disques, vous faites traverser un disque, puis vous ramenez ces n − 1 disques — deux solutions plus petites plus un coup unique. En la déroulant on obtient T(n) = 2ⁿ − 1, que l'on peut vérifier par récurrence : si T(n − 1) = 2ⁿ⁻¹ − 1 alors T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1. Résoudre la récurrence, étape par étape.

Pas au sens algorithmique, malgré le nombre exponentiel de coups. L'algorithme tient en quelques lignes, décider du coup suivant prend un temps constant, et la solution n'est exponentiellement longue que parce que la réponse l'est : afficher 2ⁿ − 1 coups ne peut pas se faire en moins de 2ⁿ − 1 étapes. Ce n'est pas NP-difficile, et trouver le plus court chemin entre deux positions légales quelconques sur trois tiges se résout aussi efficacement. La version vraiment difficile est celle à quatre tiges, dont la solution optimale, conjecturée en 1941, n'a été démontrée qu'en 2014 par Thierry Bousch. L'algorithme et ce qu'il coûte.

Avec la méthode de Frame–Stewart. Avec quatre tiges, on ne déplace plus n − 1 disques d'un bloc : on choisit une coupure k, on déplace les k disques du dessus vers une tige libre en utilisant les quatre tiges, on déplace les n − k disques restants vers l'arrivée en n'utilisant que trois tiges — la libre est occupée, donc cette partie est le casse-tête classique — puis on repose les k disques par-dessus. En essayant tous les k et en gardant le meilleur, on obtient le compte optimal, qui s'effondre spectaculairement : 15 disques passent de 32 767 coups sur trois tiges à 129 sur quatre. Jouer au casse-tête à quatre tiges.

Diviser pour régner, exprimé par la récursivité. La solution standard est une seule fonction — déplacer n − 1 disques du départ vers la tige libre, déplacer le disque n du départ vers l'arrivée, déplacer ces n − 1 disques de la libre vers l'arrivée — avec un cas de base qui ne fait rien quand n atteint zéro. Il existe un algorithme itératif équivalent, sans aucune récursivité : déplacer répétitivement le plus petit disque d'une tour dans une direction fixe, puis jouer le seul autre coup légal. Les deux produisent exactement la même suite de coups, parce que la solution optimale est unique. L'algorithme, ligne par ligne.

Une fonction récursive et trois paramètres : void hanoi(int n, char from, char to, char via) — si n vaut zéro, return ; sinon appelez hanoi(n − 1, from, via, to), affichez le coup from → to, puis appelez hanoi(n − 1, via, to, from). Appelez-la par hanoi(3, 'A', 'C', 'B'). Collectez les coups dans un std::vector<std::pair<char, char>> au lieu de les afficher si l'appelant en a besoin, et gardez n en int ordinaire : avec un paramètre non signé, un compte négatif passé par erreur devient silencieusement quelque quatre milliards, et la récursivité tourne jusqu'au débordement de pile au lieu d'échouer sur un simple test n &lt; 0. Le programme C++ complet, expliqué ligne par ligne.

Ce sont deux usages différents d'une pile, et il vaut mieux ne pas les confondre. Les tiges sont des piles : chaque tour est dernier entré, premier sorti, vous ne touchez jamais que le disque du dessus, et un coup est un dépilement d'une tour suivi d'un empilement sur une autre — d'où le fait que la vérification de la règle tienne en une seule comparaison avec le sommet de la destination. Séparément, une pile explicite peut remplacer la récursivité : empilez le travail entier (n, from, to, via), puis bouclez — dépilez un travail et, s'il lui reste des disques, empilez ses trois parties dans l'ordre inverse : le second transfert, le coup unique du disque n, puis le premier transfert. L'ordre inverse importe parce qu'une pile rend d'abord ce qui a été empilé en dernier. C'est exactement ce que l'exécution du langage fait pour vous dans la version récursive. La solution sans la moindre récursivité.

En IA, le casse-tête est un problème de recherche, pas une formule. Chaque état est une affectation de chaque disque à une tige — il y en a donc 3ⁿ — et les coups légaux sont les arêtes entre eux ; une recherche — en largeur, A* ou IDA* avec une heuristique telle que le nombre de disques pas encore sur la tige d'arrivée — trouve le plus court chemin de l'état initial au but. C'est un problème de test standard depuis le General Problem Solver de Newell, Shaw et Simon, parce que c'est un exemple limpide d'analyse moyens-fins et de décomposition d'objectifs : le sous-but « déplacer le plus grand disque » ne peut être atteint qu'en satisfaisant d'abord un sous-but qui semble défaire les progrès. À noter : l'algorithme récursif n'est pas une recherche — c'est la solution connue, et il n'explore jamais un état qu'il n'utilisera pas. Le même casse-tête comme tâche psychologique.