Ce jeu célèbre a été inventé par le mathématicien français LUCAS (1842-1891) et publié en 1892.
On considère trois tiges plantées dans une base. Au départ, sur la première tige sont enfilées N disques de plus en plus étroits. Le but du jeu est de transférer les N disques sur la troisième tige en conservant la configuration initiale.
On ne peut déplacer qu'un seul disque à la fois et il est interdit de poser un disque sur un autre plus petit.
La seconde tige est utilisée pour les stockages intermédiaires.
Il existe plusieurs algorithmes pour résoudre ce problème. Le plus évident (et le plus simple à programmer) utilise une méthode récursive.
Méthode récursive :
On suppose que l'on sait placer les N − 1 premiers disques sur la tige 2 en utilisant la tige 3 comme intermédiaire.
On déplace le Nième disque de la tige 1 vers la tige 3.
On déplace les N − 1 disques de la tige 2 vers la tige 3 en utilisant la tige 1 comme intermédiaire.
On réitère tant que N n'est pas nul.
En Javascript, on peut écrire la procédure récursive sous la forme :
|
function Transfert(N, Orig, Dest, Inter){ if (N > 0){ Transfert(N−1, Orig, Inter, Dest); Nop++; TabO[Nop] = Orig; TabD[Nop] = Dest; Transfert(N−1, Inter, Dest, Orig);}} |
Nop désigne le numéro de la manipulation en cours.
TabO et TabD sont deux tableaux contenant les positions de départ et d'arrivée pour le mouvement d'indice Nop des disques .
Ces tableaux sont utilisés pour visualiser les mouvements
On montre qu'avec cet algorithme, il faut effectuer 2N − 1 opérations pour effectuer le transfert.
On montre aussi que ce nombre d'opérations est minimal. Il croît très vite avec N.
(pour N = 64 il vaut 18 446 744 073 709 551 615).
Méthode itérative
Il existe aussi une procédure itérative optimale. Si on désigne par 1, 2 et 3 les trois tours, elle consiste à effectuer successivement les deux déplacements suivants :
− déplacer le plus petit disque d'un emplacement à l'emplacement suivant (de 1 vers 2, de 2 vers 3, de 3 vers 1) ;
− déplacer un autre disque. (action bien définie car en dehors du plus petit disque, un seul mouvement de disque est possible.)
et à continuer ces deux déplacements jusqu'à ce toute la tour soit déplacée
Utilisation :
Le programme permet soit la résolution automatique du problème (avec la méthode récursive) soit la résolution manuelle.
On peut choisir le nombre de disques N qui doit être compris entre 3 et 10.
En mode automatique le slider permet de régler la vitesse des déplacements.
Le bouton [RàZ] permet de revenir à tout moment à la configuration initiale.
En mode manuel, cliquer avec la souris dans le rectangle blanc situé sous la tige du disque que l'on désire déplacer, glisser le curseur de la souris (en maintenant le bouton enfoncé) vers le rectangle blanc situé sous la tige d'arrivée et relâcher le bouton pour effectuer le transfert.
Le programme ne permet pas de déplacer un disque sur un disque plus petit que lui.
Il n'existe pas de tours dans le vieil Hanoï mais on y trouve quelques jolies pagodes.
Voici la plus petite et sans doute la plus originale.