Jeu en Ligne: Tours de Hanoï
- Posted by Admin on 11.14.2006
- 44 comments
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 Jeu
Le problème mathématique des tours de Hanoï a été inventé par Édouard Lucas en 1883. Il le publia sous le pseudonyme de N. Claus de Siam soi-disant 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).
Selon l'auteur, le problème serait originaire d'Inde où une légende raconte que dans un temple où se trouvent trois poteaux sur lesquels s'empilent 64 disques d'or, les prêtres de Brahmâ déplacent continuellement les disques selon les règles édictées ci-dessus. D'après cette même légende, le dernier déplacement de disque marquera la fin du monde. Cette légende existe sous plusieurs versions et dans différentes religions.
Un jeu à 64 disques requiert un minimum de 264-1 déplacements, soit plus de 40 fois le nombre de secondes écoulées depuis l'origine de l'Univers. La référence à Hanoï, capitale du Viêt Nam, provient sans doute du fait que, dans cette ancienne colonie française de tradition bouddhiste, on retrouve beaucoup de pagodes dont la forme évoque l'empilement des disques de ce problème.
Un Vrai jeu en réseau
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. On notera que l'action déplacer un autre disque est non ambiguë 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 a -> c -> b -> a -> ... -> b si N est pair, et a -> b -> c -> a -> ... -> 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 a -> c -> b -> a -> ... -> 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 c -> b -> a -> c -> ... -> b. Finalement, la suite des déplacements du petit disque aura bien été a -> c -> b -> a -> ... -> c -> b -> a -> c -> ... -> b, le plus petit disque étant déplacé une fois sur deux.
- On procèdera à une vérification analogue si N est impair.
