|
Tour de Hanoi ou de Brahmâ ou tours de Hanoi Casse-tête classique dont
la résolution suit en fait le principe du codage Gros-Gray:
changer un seul élément à la fois. Même principe de résolution que le baguenaudier. Tour de Brahmâ: objet d'un culte religieux Hindouiste. Intérêt: excellent exemple de procédure récursive, régal des programmeurs. |
|
|
Jeu créé en 1883 par le français Édouard Lucas (1842-1891). Il
s'agit de la tour de Brahmâ de 64 disques simplifiée à 8 disques. Il
faut 28 – 1 = 255 coups pour le terminer. Lucas en
fait un petit livre au titre plein de mystère en 1882: La tour de
Hanoï Véritable
casse-tête annamite Jeu
rapporté du Tonkin par le professeur N. Claus (de Siam) du collège Mandarin
Li-Sou-Stian Claus est
une anagramme de Lucas et Li-Sou-Tina
de Saint Louis. Il
commence son ouvrage par: D'après une
vieille légende indienne, les brahmes se succèdent depuis bien longtemps sur
les marches de l'autel dans le temple de Bénarès pour exécuter le déplacement
de la Tour Sacré de BRAHMA aux
soixante-quatre étages en or fin, garnis de diamants de Golconde. Quand tout
sera fini, la tour et les brahmes tomberont, et ce sera la fin du monde! Le jeu
original de Lucas est conservé au Conservatoire des Arts et métiers à Paris.
Plus simple, on peut y jouer avec des pièces de
monnaies de tailles différentes. Ou encore plus simple pour enfants, avec
trois anneaux pris dans un jeu de bébés. Des rondelles de cartons peuvent
très bien faire l'affaire également. |
|
||
Avec trois supports à notre disposition, il faut faire
passer les anneaux de gauche à droite, sans que jamais un plus grand soit sur
un plus petit. Règle générale
Déplacer un à un 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 cela en un minimum de coups et sans qu'un plus gros disque
soit posé sur un plus petit. |
||
Position de départ
On note 2
l'anneau du bas et 1 celui du haut.
On symbolise la situation de départ par
trois nombres comme indiqué: 21 0 0 Étape 1
On déplace l'anneau 1 de gauche vers le
milieu
On symbolise de cette façon: 2 1 0 Étape 2
L'anneau 2 passe de gauche à droite: 0
1 2 Étape 3
Le petit anneau se place à gauche sur le
plus grand: 0
0 21 |
|
|
|
||||
Avec notre notation, voici
les mouvements.
La résolution exige sept
mouvements à partir de la position de départ. Soit 8 positions au total. |
321 32 3 3 0 1 1 0 |
0 0 2 21 21 2 0 0 |
0 1 1 0 3 3 32 321 |
|
|
|||||
Solution en 24 = 16 mouvements.
On analyse le mouvement du 1,
puis celui des autres chiffres. |
|||||
Déplacement du 1
(petit anneau) |
4321 432 43 43 4 41 |
0 1 1 0 3 3 |
0 0 2 21 21 2 |
Descente droite
Immobile
Descente droite
Immobile
Descente droite
circulaire: le 1 passe de l'autre côté |
|
Déplacement des
autres chiffres (autres anneaux) |
41 41 4 0 0 2 21 21 2 0 0 |
3 32 321 321 32 3 3 0 1 1 0 |
2 0 0 4 41 41 4 43 43 432 4321 |
Le 2 est déplacé,
c'est la seule possibilité.
Le 4 est
déplacé, c'est la seule possibilité.
Le 2 est
déplacé, c'est la seule possibilité.
Etc. |
|
|
|
La règle est simple:
Le 1
descend toujours d'un cran vers la droite, avec effet circulaire le cas échéant. Le mouvement du 1 se produit une
fois sur deux.
Dans
les autres cas, le seul chiffre qui peut bouger fait mouvement. La résolution exige 2n – 1
mouvements, si n est la quantité d'anneaux. Voir Échiquier
et les grains de blé Note Récemment, des
mathématiciens ont prouvé que, quel que soit le nombre de disques, les
déplacements ne se répètent jamais consécutivement dans le même ordre: jamais
2 fois de suite AB ou AB, AC, etc. Commentaires
Édouard Lucas a montré
qu'il y toujours une solution et que le nombre de mouvements est: 2n – 1.
La méthode exposée ci-dessus est dite itérative.
Il existe une méthode plus expéditive dite récursive. Elle est très utilisée pour illustrer
la méthode récursive de résolution des problèmes par programmation de type déclaratif. |
|
||||
Solution en 25 = 32 mouvements.
Première partie pour dégager
le 5: 16 mouvements. |
54321 5432 543 543 54 541 541 54 5 5 52 521 521 52 5 5 |
0 1 1 0 3 3 32 321 321 32 3 3 0 1 1 0 |
0 0 2 21 21 2 0 0 4 41 41 4 43 43 432 4321 |
|
Deuxième partie assez
symétrique à la première: 16 mouvements.
Pour être puriste, il
faudrait, ici, inverser colonne milieu et colonne de droite pour retrouver la
configuration désirée à droite.
Alors il faudrait changer les
règles en conséquence lorsque la quantité d'anneau est impaire. |
0 1 1 0 3 3 32 321 321 32 3 3 0 1 1 0 |
5 5 52 521 521 52 5 5 54 541 541 54 543 543 5432 54321 |
4321 432 43 43 4 41 41 4 0 0 2 21 21 2 0 0 |
|
|
|
5,8 1011 Nombre d'années
pour terminer la tour de Brahmâ. Calcul Pour les 64 disques de
la tour de Brahmâ, on montre que le nombre minimum de
mouvements est égal à 264 – 1. C'est le même nombre que pour les grains de blé de l'échiquier, soit
1,84 1019 . À raison
d'un mouvement par seconde, soit 31 558 000 mouvements par an, il faudra 584
milliards d'années (5,8 1011). Soit 42,6 fois plus que l'âge de l'Univers
estimé à 13,7 milliards d'années. Or, selon cette légende indienne, l'Univers a, à peine, vécu et il lui reste encore quelques années
à vivre! (5,8 1011 / 1,5 1010 = 38 fois l'âge de
l'Univers). Légende Dans le grand temple de Bénarès, sous le dôme qui marque le centre du
monde, repose un socle de cuivre équipé de trois aiguilles verticales en
diamant de 50 cm de haut. À la création, Dieu enfila 64 plateaux en or pur sur une des aiguilles,
le plus grand en bas et les autres de plus en plus petits. C'est la tour de
Brahmâ. Les moines doivent continûment déplacer les disques de manière que
ceux-ci se retrouvent dans la même configuration sur une autre aiguille. La règle de Brahmâ est simple: un seul disque à la fois et jamais un
grand plateau sur un plus petit. Arrivé à ce résultat, le monde tombera en poussière et disparaîtra. |
Voir Âge
de l'Univers
|
|
Trois pieux; deux jeux d'anneaux de deux couleurs.
Même règle que ci-dessus, en admettant que l'on peut
poser un anneau sur un de même taille. Solution
Ici, en 29 coups, sans doute la solution optimale: AC - BC - AB - CB -
CB - AC - BA - BA - BC - BC - AC - AC - BA - CA -
CA - CB - CB - AC - AC - BA - BA - CA - CA - CB -
AC - AC - AB - CB - CA. |
|
|
Hanoi, la "ville
au-delà du fleuve", capitale du Viêt Nam. Au Tonkin, sur le delta du
fleuve Rouge. Deuxième ville du pays après Hô-Chi-Minh-Ville.
Prise par les Français, la ville devint la capitale du protectorat
du Tonkin puis, après 1887, le siège du gouvernement de l'Indochine
française.
Le 19 mars 1946, le massacre de Français marqua le
début de la guerre d'Indochine.
Devenue la capitale du Viêt Nam du Nord en 1954, elle
fut choisie comme capitale du Viêt Nam réunifié en 1975.
Brahmâ: un des principaux
dieux du panthéon hindou,
premier créé et créateur de toute chose. Il est souvent représenté avec quatre bras et
quatre têtes qui symbolisent son omniscience et son omniprésence. |
Voir DicoCulture
|
|||
De manière récursive, la
résolution de la tour de Hanoi se réduit à ces trois règles:
Faire passer n – 1 disques
supérieurs de du support 1 au support 2.
Déplacer le nième disque, le
plus grand, du support 1 au support 3.
Faire passer n – 1 disques
du support 2 au support 3, sur le nième disque.
Résumé en formule Si M est la quantité de
mouvements à effectuer
M1 = 1
Mn = 2 x Mn-1 + 1 |
Si on sait faire cette opération, on sait
les faire toutes. |
||
On démontre par récurrence forte que: |
Mn |
= 2n – 1 |
|
Point de départ. |
M1 |
= 2 – 1 = 1 C'est vrai |
|
Hypothèse de récurrence:
relation vraie pour tous les entiers i jusqu'à k. |
Mi |
= 2i – 1 |
|
Ce qu'il faut démonter. |
Mk |
= 2k – 1 |
|
Nous connaissons la formule
de récurrence. |
Mk |
= 2 x Mk-1 + 1 |
|
Avec notre hypothèse. |
|
= 2 x (2k – 1 – 1)
+ 1 |
|
Calculs. |
|
= 2k – 2 + 1 |
|
Finalement. |
|
= 2k – 1 |
|
|
||
Le jeu à trois tiges (ou aiguilles) a été inventé en 1883. On sait que
la quantité minimale de coups vaut 2N – 1 où N est la quantité de
disques à déplacer. En 1908, Henri Dudeney propose la variante à quatre tiges et il donne
une formule indiquant le nombre de coup pour la résoudre. |
En
2014, Thierry Bousch, université d'Orsay, démontre que la formule de Dudeney
est bien la formule minimale. Spécialiste
des systèmes dynamiques, sa méthode est originale. Il construit des chemins
dans le graphe des possibilités. Il analyse des systèmes perturbés: sur la
tige initiale, il manque des disques sans que l'on sache lesquels… |
|
La formule de Dudeney donnant la quantité de mouvements pour N disques
sur quatre tiges: |
avec delta n, la racine triangulaire par défaut de n,
c'est-à-dire le plus grand entier p tel que: |
|
Anglais: four-peg variant of the Towers of Hanoi
|
||
Présentation Similaire à la tour de Hanoï
à quatre tiges, mais la quatrième est centrale, et elle sert de pivot aux
mouvements: une pièce ne peut être déplacée que vers la tige centrale ou de
la tige centrale vers une des trois tiges périphériques. |
Le jeu Source
image: La tour de Stockmeyer
– Maths-en-Jeans |
|
Quantité de mouvements La solution minimale avec quatre disques exige vingt mouvements. Avec cinq disques, il en faut au minimum trente-deux. Historique C'est en 1994 que Paul Stockmeyer propose cette variante de la tour de
Hanoï. Il a conjecturé, comme E. Dudeney, que la quantité minimale de
mouvements est le double de la somme des nombre 3-friables. La preuve en a
été apportée en 2017 par Thierry Boush. |
Nombres 3-friables La quantité de mouvements pour k disques est égale au double de la
somme des k plus petits nombres
3-friables. Ces nombres sont de la forme 2a٠3b. Ces sont 1, 2, 3, 4, 6, 8, 9, 12 … dont la double-somme pour k = 4 est
20, et celle pour k = 5 est 32. |
|
Anglais: In 1994, Paul Stockmeyer proposed a four-peg variant
of the Tower of Hanoi puzzle
Voir Brève 56-1101
Solution de la tour de Stockmeyer
Illustration présente en
Les entiers friables – Jean-Paul Delahaye – Pour la Science N539 septembre 2022
Voir |
||
Livre |
Les tours de Hanoï, plus qu'un jeu
d'enfants
– Jean-Paul Delahaye – Pour la Science Novembre 2015
Ce
livre de 2013 est en lecture gratuite sur Internet pour certaines pages (illustration) |
|
Sites |
Tours de
Hanoi sur Wikipédia pour compléments sur les méthodes itératives et
récursives La quatrième
tour de Hanoï – Thierry Boush – 2014 Récursion - Tours de Hanoï
– Christian Queinnec – Vidéo La
tour de Stockmeyer – Thierry Boush – Paris-Saclay OEIS A341579 - Number of steps needed to
solve the Towers of Hanoi exchanging disks puzzle with 3 pegs and n disks OEIS A160002 – Number of moves needed to
solve 4-peg Tower of Hanoi Puzzle with n disks. |
|
Cette page |