Les tours de Hanoï

Les Tours de Hanoï sont un casse-tête mathématique classique composé de trois piquets et d’un ensemble de disques de tailles différentes. Au départ, tous les disques sont empilés sur un seul piquet par ordre décroissant de taille, le plus grand en bas et le plus petit en haut. L'objectif est de déplacer l'ensemble de la pile sur un autre pieu, en respectant des règles strictes concernant la manière dont les disques peuvent être déplacés. Le nombre minimal de mouvements nécessaires pour résoudre un casse-tête comportant N disques est égal à 2^N - 1.

Règles

1. Trois piquets (ou tours) sont disposés côte à côte.
2. Un certain nombre de disques de tailles différentes sont empilés sur un piquet, classés du plus grand (en bas) au plus petit (en haut).
3. Un seul disque peut être déplacé à la fois.
4. Chaque déplacement consiste à retirer le disque du haut d’un piquet et à le placer au sommet d’un autre piquet.
5. Un disque plus grand ne peut jamais être placé au-dessus d’un disque plus petit.
6. Le but est de déplacer toute la pile du piquet de départ vers le piquet d’arrivée.

Stratégies

• Approche récursive : pour déplacer N disques de la broche A vers la broche C en utilisant la broche B comme auxiliaire : déplacez d’abord les N-1 disques du haut de A vers B, puis déplacez le plus grand disque de A vers C, puis déplacez les N-1 disques de B vers C.
• Modèle itératif : Lors des coups impairs, déplacez le plus petit disque. Lors des coups pairs, effectuez le seul déplacement autorisé qui n’implique pas le plus petit disque. Le plus petit disque se déplace toujours dans le même sens de rotation (A→B→C→A pour un nombre impair de disques, A→C→B→A pour un nombre pair).
• Comptage binaire : La séquence de déplacements correspond à un comptage binaire. Le disque à déplacer à l’étape K est déterminé par la position du bit le plus bas activé dans la représentation binaire de K.
• Commencez petit : Entraînez-vous avec 3 disques (7 déplacements) avant de vous attaquer à des nombres plus grands. Le schéma devient intuitif dès lors que vous le voyez se répéter.
• Algorithme de Frame-Stewart : pour les variantes comportant plus de 3 piquets, l’algorithme de Frame-Stewart fournit des solutions supposées optimales, bien que l’optimalité n’ait été prouvée que pour 4 piquets.

Le casse-tête des Tours de Hanoï a été inventé en 1883 par le mathématicien français Édouard Lucas, qui l'a publié sous le pseudonyme de « Professeur N. Claus de Siam » (un anagramme de « Lucas d'Amiens »). Ce casse-tête était vendu comme un jouet, accompagné d'une légende selon laquelle, dans un temple de Bénarès (Varanasi), en Inde, des prêtres brahmanes travaillaient sur une version comportant 64 disques d'or enfilés sur des aiguilles en diamant. Selon cette légende, lorsque les prêtres auraient résolu le casse-tête, ce serait la fin du monde. À un rythme optimal d’un mouvement par seconde, la version à 64 disques nécessiterait 2^64 - 1 mouvements, soit environ 585 milliards d’années, ce qui est bien plus long que l’âge estimé de l’univers.

Ce casse-tête est rapidement devenu un incontournable des mathématiques ludiques. Ce fut l’un des premiers casse-têtes à faire l’objet d’une analyse approfondie à l’aide du concept alors émergent de récursivité, et il reste l’un des exemples les plus importants dans l’enseignement de l’informatique pour aborder les algorithmes récursifs, l’induction mathématique et la complexité algorithmique.

Au-delà de son rôle d’outil pédagogique, les Tours de Hanoï entretiennent des liens étroits avec d’autres domaines des mathématiques. L’espace d’états du casse-tête forme un graphe du triangle de Sierpinski, ce qui le relie à la géométrie fractale. Le casse-tête trouve également des applications dans les schémas de rotation des sauvegardes (la stratégie de sauvegarde dite « des Tours de Hanoï »), les codes de Gray et l’analyse de certains algorithmes de tri.

Parmi les variantes du casse-tête, on trouve le problème de Frame-Stewart (utilisant 4 piquets ou plus), des variantes colorées où les disques doivent aboutir à une disposition spécifique, et des versions bicolores où deux ensembles entremêlés de disques doivent être séparés. Ce casse-tête a été adapté dans de nombreux jeux vidéo, où il apparaît comme un mécanisme récurrent dans les jeux d’aventure, les jeux de rôle et les compilations de casse-têtes. Il a occupé une place importante dans l'épisode de Doctor Who de 1966 intitulé « The Celestial Toymaker » et est apparu dans des films tels que « La Planète des singes : Les Origines » (2011) comme test de capacités cognitives.