Tours de Hanoï

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Un modèle d'une Tour d'Hanoï (avec 8 disques)
Étapes de la résolution du problème avec 4 disques.

Le problème des tours de Hanoï est un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer des disques de diamètres différents d'une tour de « départ » à une tour d'« arrivée » en passant par une tour « intermédiaire », et ceci en un minimum de coups, tout en respectant les règles suivantes :

  • on ne peut déplacer plus d'un disque à la fois,
  • on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.

On suppose que cette dernière règle est également respectée dans la configuration de départ.

Origine du problème[modifier | modifier le code]

Le problème mathématique des tours de Hanoï a été inventé par Édouard Lucas. Il est publié dans le tome 3 de ses Récréations mathématiques, parues à titre posthume en 1892. Il annonce que ce problème est dû à un de ses amis, N. Claus de Siam, prétendument professeur au collège de Li-Sou-Stian (une double anagramme de Lucas d'Amiens, sa ville de naissance, et Saint Louis, le lycée où Lucas enseignait).

Sous le titre « Les brahmes tombent », Lucas relate que « N. Claus de Siam a vu, dans ses voyages pour la publication des écrits de l'illustre Fer-Fer-Tam-Tam, dans le grand temple de Bénarès, au-dessous du dôme qui marque le centre du monde, trois aiguilles de diamant, plantées dans une dalle d'airain, hautes d'une coudée et grosses comme le corps d'une abeille. Sur une de ces aiguilles, Dieu enfila au commencement des siècles, 64 disques d'or pur, le plus large reposant sur l'airain, et les autres, de plus en plus étroits, superposés jusqu'au sommet. C'est la tour sacrée du Brahmâ. Nuit et jour, les prêtres se succèdent sur les marches de l'autel, occupés à transporter la tour de la première aiguille sur la troisième, sans s'écarter des règles fixes que nous venons d'indiquer, et qui ont été imposées par Brahma. Quand tout sera fini, la tour et les brahmes tomberont, et ce sera la fin des mondes ![1] ».

Comme indiqué ci-dessous, un jeu à 64 disques requiert un minimum de 264-1 déplacements. En admettant qu'il faille 1 seconde pour déplacer un disque, ce qui fait 86 400 déplacements par jour, la fin du jeu aurait lieu au bout d'environ 213 000 milliards de jours, ce qui équivaut à peu près à 584,5 milliards d'années, soit 43 fois l'âge estimé de l'univers (13,7 milliards d'années selon certaines sources)[2].

Nombre de déplacements à effectuer[modifier | modifier le code]

Il est facile de démontrer par récurrence que si n est le nombre de disques, il faut 2n - 1 coups au minimum pour parvenir à ses fins[3], quantité qui augmente très rapidement avec n. En effet, soient A, B et C les trois emplacements des tours ; notons xn le nombre de déplacements de disques nécessaires au déplacement d'une tour complète. Pour déplacer une tour de n disques de A vers C, on effectue ces trois étapes :

  • déplacer la tour des n-1 premiers disques de A vers B (étape qui nécessite xn-1 déplacements, d’où la récurrence) ;
  • déplacer le plus grand disque de A vers C (un déplacement supplémentaire) ;
  • déplacer la tour des n-1 premiers disques de B vers C (à nouveau xn-1 déplacements).

Le nombre de déplacements de disques vérifie donc la relation de récurrence :


\left\{\begin{matrix}
x_0 &=& 0 \\
x_n &=& 2x_{n-1} + 1 &\mbox{si }n\geq1
\end{matrix}\right.

ce qui donne bien

x_n=2^n-1\,

On peut montrer que la méthode décrite ici donne la séquence optimale (celle qui nécessite le moins de coups), et que celle-ci est unique. En effet, pour déplacer la tour de n disques de A vers C, on devra forcément, à un moment ou à un autre, déplacer le plus grand disque de A vers C, et pour ce faire, on devra avoir empilé les n-1 premiers disques en B.

Résolution algorithmique[modifier | modifier le code]

Solution récursive[modifier | modifier le code]

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

Algorithme généralisé à une position quelconque[modifier | modifier le code]

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 Pk 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 Pn 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 Pn) ;
  • déplacer le plus grand disque de Pn 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 (Pn = 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 yn(A).

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

On a donc la relation de récurrence suivante :


\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\geq1
\end{matrix}\right.

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

y_n = \sum_{k=1}^n b_k \times 2^{k-1}

bk 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 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.

Solution itérative[modifier | modifier le code]

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.

Une autre solution itérative[modifier | modifier le code]

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 \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 \frac{2^n-2}{3} fois puis se termine par le déplacement de la tour 1 vers la tour 3).

Codage des positions[modifier | modifier le code]

Nous avons vu que, si p est impair, le p-ème coup consiste à déplacer le plus petit disque. Nous avons également vu que le déplacement du petit disque était cyclique. Par ailleurs, si p est pair, on vient de déplacer un autre disque, le plus petit disque ayant été déplacé au coup p-1 ; le disque que l'on vient de déplacer au coup p l'aurait été au coup p/2 s'il n'y avait eu que N-1 disques.

Il résulte de ces préliminaires que, pour connaître la disposition des disques après le p-ème déplacement, il suffit de procéder comme suit.

Notons d(N,p) la position du plus petit disque après le p-ème coup (p impair), on a :

d(N,1) = d(N,7) = … = d(N,1+3k) = B si N est impair et = C si N est pair.
d(N,3) = d(N,9) = … = d(N,3k) = C si N est impair et = B si N est pair.
d(N,5) = d(N,11) = … = d(N,2+3k) = A.

Notons E(N,p) la suite des emplacements occupés par les N disques, du plus grand au plus petit, après p mouvements. On a alors, en notant par un point la concaténation entre deux listes de lettres :

Si p est pair, égal à 2m, E(N,2m) = E(N-1,m).d(N,2m-1)
Si p est impair, égal à 2m+1, E(N,2m+1) = E(N-1,m).d(N,2m+1)

Par exemple, la position au 12e coup avec 4 disques est :

E(4,12) = E(3,6).d(4,11) = E(3,6).A
= E(2,3).d(3,5).A = E(2,3).AA
= E(1,1).d(2,3).AA = E(1,1).BAA
= BBAA

Tours de Hanoï et Triangle de Pascal[modifier | modifier le code]

Graphe des tours de Hanoï, avec 3 disques
Graphe obtenu à partir du Triangle de Pascal

On peut représenter le jeu des Tours de Hanoï par un graphe abstrait, chaque sommet du graphe représentant une disposition possible des N disques sur les trois tours, une arête reliant deux sommets s'il existe un mouvement d'un disque permettant de passer d'une disposition, représentée par l'un des sommets, à l'autre. L'étiquetage des sommets est basé sur la position des disques dans la disposition qu'il représente : on lit de gauche à droite à quelle tour appartient chaque disque, en commençant par la position du plus grand disque.

Le diagramme montre l'arbre du jeu avec trois disques. La position initiale est située à l'un sommets du triangle, par exemple AAA, la position finale étant un autre sommet, BBB ou CCC. La couleur des arêtes indique le disque à déplacer : rouge pour le plus petit disque, jaune pour le disque intermédiaire, et bleu pour le grand disque.

On montre que, pour tout N, le graphe des Tours de Hanoï à N disques est identique à celui obtenu à partir d'un Triangle de Pascal d'ordre 2N, où l'on relie par une arête les coefficients binomiaux impairs[4].

Applications[modifier | modifier le code]

La tâche de la Tour de Hanoï est utilisée dans la recherche en psychologie notamment au travers de la résolution de problème.

Cette tâche est sensible aux dysfonctionnements frontaux et préfrontaux[5],[6].

Ce test permet ainsi l'évaluation des fonctions exécutives[7], comme la planification[5], la mémoire de travail[8] et l'inhibition[9].

La performance à la tour d’Hanoï dépend des capacités d'inhibition[10], de la mémoire de travail[11], de la mémoire procédurale[12], et de l'intelligence fluide[13].

Or l'inhibition nécessite la suppression de l'activité du cortex moteur primaire, du cortex frontal inférieur droit et de l'aire motrice supplémentairement[14]. La mémoire de travail implique la partie dorso-latérale du cortex frontal qui permet la manipulation active et le contrôle des informations[15]. De même, la planification est corrélée avec l'activation de la partie dorsale du cortex préfrontal, du cortex pariétal et prémoteur et du cerebellum[16].

On comprend pourquoi la tour d'Hanoï est sensible aux dysfonctionnements frontaux et préfontaux[5].


Ce test est proche de celui du test de la Tour de Londres ainsi que celui des Tours de Toronto[17].

Notes et références[modifier | modifier le code]

  1. Édouard Lucas, Récréations mathématiques, tome 3, (1892), réédité par la Librairie Albert Blanchard, (1979), p. 58
  2. Le nombre exact de secondes nécessaires (18 446 744 073 709 551 615) est égal au nombre de grains de blé demandés, selon une autre légende indienne, par le brahmane Sissa au roi Belkib comme récompense pour avoir inventé le jeu d'échecs, qui se joue sur 64 cases.
  3. Pour résoudre le problème plus général du nombre de déplacements à effectuer pour déplacer n disques au moyen d'un nombre de tours autre que trois, voir J.S.Frame, B.M.Stewart, A solution to Monthly problem 3918, Amer. Math. Monthly 48 (1941) 216-219
  4. A.M.Hinz, Pascal's triangle and the tower of Hanoï, Amer. Math. Monthly 9 (1992) 538-544
  5. a, b et c (en) V. Goel et J. Grafman, « Are the frontal lobes implicated in planning functions? Interpreting data from the Tower of Hanoi. », Neuropsychologie, vol. 33, no 5,‎ 1995, p. 623-642
  6. (en) D. T. Stuss et D. F. Benson, « Neuropsychological studies of the frontal lobes », Psychological Bulletin, vol. 95, no 1,‎ 1984, p. 3-28
  7. (en) Goldstein, F. C. et Green, R. C., « Assessment of problem solving and executive functions. Clinical neuropsychological assessment: A cognitive approach. », Critical issues in neuropsychology,‎ 1995, p. 49–81
  8. (en) V. Goel, S. D. Pullara et J. Grafman, « A computational model of frontal lobe dysfunction: Working memory and the Tower of Hanoi task », Cognitive Science, vol. 25, no 2,‎ 2001, p. 287-313
  9. (en) Pennington, B. F., Bennetto, L., McAleer, O. et Roberts Jr., Attention, memory, and executive function : Executive functions and working memory: Theoretical and measurement issues,‎ 1996, 327–348 p.
  10. (en) M. C. Welsh, T. Satterlee Cartmell et M. Stine, « Towers of Hanoi and London: Contribution of working memory and inhibition to performance », Brain and Cognition, vol. 41, no 2,‎ 1999, p. 231-242
  11. (en) S. J. Handley, A. Capon et C. Harper, « Conditional reasoning and the Tower of Hanoi: The role of spatial and verbal working memory », British Journal of Psychology, no 93,‎ 2002, p. 501-518
  12. (en) A. Bagley, M. C. Welsh, P. Retzlaff et E. Bryan, « Towers of Hanoi and London: Contribution of procedural learning and inhibition », Journal of the International Neuropsychological Society, vol. 8, no 2,‎ 2002, p. 229
  13. (en) S. Devine, M. C. Welsh, P. Retzlaff, M. Yoh et C. Adams, « Explicit and implicit cognitive processes underkying Tower of Hanoi performance », Journal of the International Neuropsychological Society, vol. 7, no 2,‎ 2001, p. 250
  14. (en) Zandbelt B., M. Bloemendaal, J. Hoogendam, R. Kahn et M. Vink, « Transcranial magnetic stimulation and functional MRI reveal cortical and subcortical interactions during stop-signal response inhibition », Journal Of Cognitive Neuroscience, vol. 25, no 2,‎ 2013, p. 157-174 (DOI 10.1162/jocn_a_0030)
  15. (en) C. E. Curtis, D. H. Zald et J. V. Pardo, « Organization of working memory within the human prefrontal cortex: a PET study of self-ordered object working memory », Neuropsychologia, vol. 38, no 11,‎ 2000, p. 1503-1510
  16. (en) J. Rowe, A. Owen, I. Johnsrude et R. Passingham, « Imaging the mental components of a planning task. », Neuropsychologia, vol. 39, no 3,‎ 2001, p. 315-327
  17. (en) R. Parks et J. Cardoso, « Parallel distributed processing and executive functioning : Tower of Hanoi neural networkmodel in healthy controls and left frontal lobe patients. », International journal of neuroscience, vol. 89, no 3-4,‎ 1997, p. 217-240

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

  • Panex, où il faut échanger 2 piles de disques de couleurs différentes.

Liens externes[modifier | modifier le code]