Tour d'Hanoï

Tour d'Hanoï

Tours de Hanoï

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

Sommaire

Origine du problème

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

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, ce qui augmente très rapidement le temps nécessaire pour résoudre ce problème. 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 déplace la tour des N-1 premiers disques de a vers b, puis le disque N de a vers c, puis la tour des N-1 disques de b vers c. Le nombre de déplacements de disques vérifie donc la relation de récurrence :


\left\{\begin{matrix}
x_1=1, \\
x_N = 2x_{N-1} + 1, & \mbox{si }N>1
\end{matrix}\right.

ce qui donne bien

x_N=2^N-1\,

Résolution récursive

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 Déplacer sont :

nombre : nombre de disques utilisés
de : emplacement de départ
à : emplacement de destination
par : emplacement intermédiaire
sub Déplacer (nombre, de, à, par)
    si nombre > 0 alors
                  Déplacer nombre - 1, de, par, à;
                  Bouger-un-disque de, à;
                  Déplacer nombre - 1, par, à, de;
    fin-du-si
fin-du-sub

On obtient par exemple :

En langage PHP

 function hanoi($nbr, $dep, $fin, $int)
 {
   if($nbr > 0)
   {
     hanoi($nbr - 1, $dep, $int, $fin);
     echo "D".$nbr.":".$dep."->".$fin."&nbsp";
     hanoi($nbr - 1, $int, $fin, $dep);
   }
 }

En langage Python :

def hanoi(n,de,a,par):
    if n>0:
        hanoi(n-1, de, par, a)
        print str(de),"-->",str(a)
        hanoi(n-1, par, a, de)
 
print """
jeu de hanoi
il s'agit de deplacer des disques
de la tour 1 vers la tour 2
"""
n = input("donner le nombre de disques : ")
hanoi(n,1,2,3)

Résolution itérative

Il existe également une procédure itérative pour résoudre le problème des tours de Hanoï. Elle consiste à effectuer successivement les deux déplacements suivants :

  • 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 ambigüe puisque, en dehors du plus petit disque, un seul mouvement d'un autre 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. Par contre, les raisons pour lesquelles cet algorithme résout le problème sont moins apparentes que pour l'algorithme récursif.

Supposons que la tour soit initialement sur l'emplacement a, et qu'on veuille la déplacer sur l'emplacement b. Nous allons montrer par récurrence sur le nombre N de disques à déplacer que l'itération des deux mouvements décrits précédemment répond à la question, le sens dans lequel est déplacé le plus petit disque étant acba → … → b si N est pair, et abca → … → b si N est impair. En effet :

  • Pour N = 1, il suffit de déplacer l'unique disque de a vers b. 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 c, puis le grand disque de a vers b, puis les N-1 disques de c vers b.
  • Si N est pair, alors N-1 est impair, et selon l'hypothèse de récurrence (en échangeant les rôles de b et c), lors du déplacement de la pile des N-1 disques supérieurs de a vers c, un déplacement sur deux est effectué par le plus petit disque dans l'ordre acba → … → c. On déplace alors le grand disque de a vers b (déplacement qui succède au dernier déplacement du plus petit disque). Puis on déplace les N-1 disques de c vers b, un déplacement sur deux étant effectué par le plus petit disque, cette fois dans l'ordre cbac → … → b. Finalement, la suite des déplacements du petit disque aura bien été acba → … → cbac → … → b, le plus petit disque étant déplacé une fois sur deux.
  • On procédera à une vérification analogue si N est impair.

Codage des positions

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 p2 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 disques, du plus grand au plus petit. 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

Applications

Les problèmes de la forme des Tours de Hanoï sont utilisés dans la recherche en psychologie de la résolution de problème. Ils peuvent aussi être employés comme épreuves lors d'une évaluation neuropsychologique des fonctions exécutives, en particulier sous la forme du test de la Tour de Londres.


Notes et références

  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.

Voir aussi

Article connexe

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

Liens externes

  • Portail des jeux Portail des jeux
  • Portail de l’informatique Portail de l’informatique
  • Portail des mathématiques Portail des mathématiques

Ce document provient de « Tours de Hano%C3%AF ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Tour d'Hanoï de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Tour de Hanoï — Tours de Hanoï É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 …   Wikipédia en Français

  • Hanoi (album) — Hanoï (album) Pour les articles homonymes, voir Hanoï (homonymie). Hanoï Album live par Indochine Sortie 19 février 2007 E …   Wikipédia en Français

  • Hanoi — Thành phố Hà Nội   Centrally governed city   Clockwise from top: Turtle Tower in Hoan Kiem Lake, in central Hanoi; …   Wikipedia

  • Tour de Keangnam Hanoi Landmark — Tour de Keangnam Hanoï Landmark Tour de Keangnam Hanoï Landmark Usage(s) Bureaux Localisation Hanoï  Viêt Nam Dates 2007 2010 …   Wikipédia en Français

  • Tour de keangnam hanoï landmark — Usage(s) Bureaux Localisation Hanoï  Viêt Nam Dates 2007 2010 …   Wikipédia en Français

  • Hanoi — Hanoï Pour les articles homonymes, voir Hanoï (homonymie). Hanoï Administration Pays …   Wikipédia en Français

  • Tour de Keangnam Hanoï Landmark — Localisation Localisation Hanoï Coordonnées …   Wikipédia en Français

  • Tour préliminaire de la coupe du monde de football 2010 : Zone AFC-Premier tour — Le tirage au sort eut lieu le 6 août 2007 au siège de l AFC à Kuala Lumpur, Malaisie. Resultats 22 octobre 2007 19:30 UTC+5 …   Wikipédia en Français

  • Hanoi Rocks — Infobox musical artist Name = Hanoi Rocks Img capt = In concert, September 2005 Img size = 250 Landscape = Yes Background = group or band Origin = Helsinki, Finland Genre = Glam punk Hard rock Years active = 1979 1985 2002 present Label = Liquor… …   Wikipedia

  • Hanoï (album) — Pour les articles homonymes, voir Hanoï (homonymie). Hanoï Live par Indochine Sortie 19 février 2007 Enregistrement …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”