Tours de Hanoï

Le problème des tours de Hanoï est vu en algorithmique (programmation), où il offre un exemple de la puissance et de la lisibilité des programmes définis de façon récursive (un autre exemple étant le tri arborescent). En effet, la méthode de résolution vue précédemment conduit à un algorithme récursif, décrit ci-dessous. Les paramètres de la procédure Hanoï sont :

• n : nombre de disques utilisés,
• D : emplacement de départ,
• A : emplacement d'arrivée,
• I : emplacement intermédiaire.

procédure Hanoï(n, D, A, I)
    si n ≠ 0
        Hanoï(n-1, D, I, A)
        Déplacer le disque de D vers A
        Hanoï(n-1, I, A, D)
    fin-si
fin-procédure

On peut généraliser la résolution récursive au cas où les disques sont initialement disposés de façon aléatoire sur les trois emplacements, plutôt qu’empilés sur le premier (la position initiale est quelconque). L’objectif sera de regrouper les n disques sur l’emplacement d’arrivée A. On numérote les n disques de 1 à n par ordre de taille croissante, et l’on note P_k la position du disque numéroté k. On part du constat suivant : il faudra forcément, à un moment, déplacer le plus grand disque de P_n vers A. Le raisonnement récursif est alors similaire au précédent :

• regrouper les n-1 premiers disques sur l’emplacement intermédiaire I (celui qui n’est ni A ni P_n) ;
• déplacer le plus grand disque de P_n vers A ;
• regrouper les n-1 premiers disques en A.

À la différence du cas particulier traité précédemment, l’emplacement de départ dépend de la disposition des disques. Il faut par ailleurs distinguer le cas où le disque n se trouve déjà au bon endroit (P_n = A). Dans ce cas, suivre la méthode précédente ne serait pas optimal : la deuxième étape est inutile, et l’on peut fusionner les première et troisième étapes en regroupant directement les n-1 premiers disques en A.

L’algorithme généralisé devient donc :

procédure Hanoï-généralisé(n, A)
    si n ≠ 0
        si Pn = A
            Hanoï-généralisé(n-1, A)
        sinon
            Hanoï-généralisé(n-1, I)
            Déplacer le disque de Pn vers A
            Hanoï-généralisé(n-1, A)
        fin-si
    fin-si
fin-procédure

Notons que le dernier appel récursif peut être remplacé par un appel à la procédure Hanoï du cas particulier vu précédemment, puisque tous les n-1 premiers disques sont alors empilés en I.

Avec le même raisonnement que précédemment, on montre que cet algorithme donne l’unique séquence optimale. On peut exprimer le nombre de coups en fonction du nombre n de disques, de leur disposition et de l’emplacement A d’arrivée : on le note y_n(A).

• Si le disque n est déjà bien placé, alors le nombre de coups est y_n-1(A) car on se contente de déplacer les n-1 premiers disques en A ;
• sinon, le nombre de coups est ${\displaystyle y_{n-1}({\mbox{I}})+1+x_{n-1}}$, soit ${\displaystyle y_{n-1}({\mbox{I}})+1+(2^{n-1}-1)}$.

On a donc la relation de récurrence suivante :

${\displaystyle \left\{{\begin{matrix}y_{0}({\mbox{A}})&=&0\qquad \qquad \qquad \qquad \qquad \quad \\y_{n}({\mbox{A}})&=&\left\{{\begin{matrix}y_{n-1}({\mbox{A}})&{\mbox{si P}}_{n}={\mbox{A}}\\y_{n-1}({\mbox{I}})+2^{n-1}&{\mbox{sinon}}\qquad \end{matrix}}\right.&\quad {\mbox{, si }}n\geq 1\end{matrix}}\right.}$

On peut alors exprimer y_n(A) comme une somme de puissances de 2, où un terme est ajouté si et seulement si le disque correspondant est mal placé :

${\displaystyle y_{n}=\sum _{k=1}^{n}b_{k}\times 2^{k-1}}$

où b_k vaut 0 si le disque k est bien placé, 1 sinon.

Dans le pire des cas, tous les disques sont mal placés. On a alors ${\displaystyle y_{n}=\sum _{k=1}^{n}2^{k-1}=2^{n}-1}$. Il est intéressant de remarquer que la situation initiale usuelle est l’un de ces pires des cas.

Il existe également une procédure itérative pour résoudre le problème des tours de Hanoï, et ce de façon optimale. Elle consiste à effectuer successivement les deux déplacements suivants, en désignant par A, B, C les trois tours (de gauche à droite) :

• déplacer le plus petit disque d'un emplacement à l'emplacement suivant (de A vers B, de B vers C, de C vers A, par exemple) ;
• déplacer un autre disque ;

et à poursuivre itérativement ces deux déplacements jusqu'à ce que la tour complète soit déplacée, le dernier déplacement se limitant alors à celui du plus petit disque sur le sommet de la tour. L'action « déplacer un autre disque » est non ambiguë puisque, en dehors du plus petit disque, un seul mouvement de disque est possible.

Contrairement à la procédure récursive, la procédure itérative n'utilise aucune mémorisation de l'arbre des déplacements à effectuer et nécessite seulement de se souvenir si on doit déplacer le plus petit disque ou non, et dans quel sens sont effectués les déplacements du petit disque. Il permet également, à tout moment, de revenir à la situation de départ : il suffit pour cela d'inverser le sens dans lequel se déplace le plus petit disque. Cependant, les raisons pour lesquelles cet algorithme résout le problème sont moins apparentes que pour l'algorithme récursif.

On peut l’expliquer en constatant que dans la solution optimale, on déplace nécessairement le plus petit disque une fois sur deux exactement, car le déplacer deux fois de suite ne serait pas optimal, et déplacer l’autre disque deux fois de suite non plus. Il reste à déterminer la façon dont on déplace ce plus petit disque.

Supposons que la tour de n disques soit initialement sur l’emplacement A, et qu’on veuille la déplacer sur l’emplacement C. On montre par récurrence sur n que l’itération des deux mouvements décrits précédemment produit la séquence optimale, si le sens dans lequel est déplacé le plus petit disque est A → B → C → A (de la gauche vers la droite) pour n pair, ou A → C → B → A (de droite à gauche) pour n impair. En effet :

• Pour n = 1, il suffit de déplacer l'unique disque de A vers C.
• Supposons la propriété démontrée pour le déplacement de n-1 disques. Comme dans le cas récursif, on va déplacer la tour de n disques en déplaçant les n-1 disques supérieurs de A vers B, puis le grand disque de A vers C, puis les n-1 disques de B vers C.
  • Si n est pair, alors n-1 est impair, et selon l'hypothèse de récurrence (en échangeant les rôles de C et B), lors du déplacement de la pile des n-1 disques supérieurs de A vers B, un déplacement sur deux est effectué par le plus petit disque dans l'ordre A → B → C → A → ... → A → B. On déplace alors le grand disque de A vers C (déplacement qui succède au dernier déplacement du plus petit disque). Puis on déplace les n-1 disques de B vers C, un déplacement sur deux étant effectué par le plus petit disque, cette fois dans l'ordre B → C → A → B → ... → B → C. Finalement, la suite des déplacements du petit disque aura bien été A → B → C → A → … → B puis B → C → A → … → C, le plus petit disque étant déplacé une fois sur deux.
  • La vérification est analogue si n est impair.

On suppose les tours numérotées 1, 2 et 3.

Un déplacement de la tour n° i vers la tour n° j est noté i + j.

Ainsi le déplacement 3 désigne aussi bien le déplacement de la tour 1 vers la tour 2 que de la tour 2 vers la tour 1, mais il n'y a pas d'ambiguïté possible : on disposera le plus petit disque sur le plus grand.

De même le déplacement 4 désigne aussi bien le déplacement de la tour 1 vers la tour 3 que de la tour 3 vers la tour 1.

Et enfin le déplacement 5 désigne aussi bien le déplacement de la tour 2 vers la tour 3 que de la tour 3 vers la tour 2.

Lorsque le nombre de disques est pair, les déplacements à effectuer sont 3,4,5,3,4,5,3,4,5... autant de fois que nécessaire (la séquence 3,4,5 est répétée ${\displaystyle {\frac {2^{n}-1}{3}}}$ fois).

Lorsque le nombre de disques est impair, les déplacements à effectuer sont 4,3,5,4,3,5,...autant de fois que nécessaire (la séquence 4,3,5 est répétée ${\displaystyle {\frac {2^{n}-2}{3}}}$ fois puis se termine par le déplacement de la tour 1 vers la tour 3).

Résolution du problème des tours de Hanoï, en s'aidant de l'alternance Noir et Blanc des disques.

On suppose les disques colorés en noir en blanc, alternativement. Par commodité, on supposera aussi que les socles des trois tiges sont colorés en noir ou blanc. Le socle qui supporte la tour initiale est colorée d'une couleur autre que celle du plus grand disque, de façon à respecter l'alternance des couleurs. Les deux autres socles sont l'un noir, l'autre blanc. On déplace itérativement les disques selon les deux règles suivantes[3] :

• On n'effectue jamais un mouvement qui annule directement le dernier mouvement qu'on vient d'effectuer.
• On déplace le seul disque qu'on peut poser sur un disque ou un socle de couleur différente.

• Panex, où il faut échanger 2 piles de disques de couleurs différentes.
• Jeu du baguenaudier
• Bézette
• Tri de crêpes

(en) Andreas M. Hinz, Sandi Klavžar et Uroš Milutinović, The Tower of Hanoi – Myths and Maths, Bâle, Springer Science & Business Media, 2013, 335 p. (ISBN 978-3-0348-0237-6, lire en ligne).