Tours de Hanoï - Définition

Introduction

É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

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 ! ».

Comme indiqué ci-dessous, un jeu à 64 disques requiert un minimum de 2⁶⁴-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).

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." ";           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)      

En langage Prolog :

      hanoi(0,De,A,Par).      hanoi(N,De,A,Par):-        N>0,         M is N-1,         hanoi(M,De,Par,A),         writeln([De, '=>', A]),        hanoi(M,Par,A,De).