La tour de Hanoi - Tower of Hanoi

Une maquette de la Tour de Hanoï (avec 8 disques)
Une solution animée du puzzle Tour de Hanoï pour T (4, 3)
Exposition interactive de la tour de Hanoï au musée Universum de Mexico

La Tour de Hanoi (aussi appelé Le problème de Bénarès Temple ou Tour de Brahma ou Tour de Lucas et parfois pluralisation comme Tours , ou simplement casse - tête pyramide ) est un jeu mathématique ou casse - tête composé de trois barres et un certain nombre de disques de différents diamètres , qui peut glisser sur n'importe quelle tige. Le puzzle commence avec les disques empilés sur une tige par ordre de taille décroissante, le plus petit en haut, se rapprochant ainsi d'une forme conique . L'objectif du puzzle est de déplacer toute la pile jusqu'à la dernière tige, en obéissant aux règles suivantes :

  1. Un seul disque peut être déplacé à la fois.
  2. Chaque mouvement consiste à prendre le disque supérieur d'une des piles et à le placer au-dessus d'une autre pile ou sur une tige vide.
  3. Aucun disque ne peut être placé sur un disque plus petit que lui.

Avec 3 disques, le puzzle peut être résolu en 7 mouvements. Le nombre minimal de mouvements requis pour résoudre un puzzle de la Tour de Hanoï est de 2 n − 1, où n est le nombre de disques.

Origines

Le puzzle a été introduit en Occident par le mathématicien français Édouard Lucas en 1883. De nombreux mythes concernant la nature ancienne et mystique du puzzle ont surgi presque immédiatement, dont un sur un temple indien à Kashi Vishwanath contenant une grande pièce avec trois messages dedans, entourés de 64 disques d'or. Exécutant l'ordre d'une ancienne prophétie, les prêtres brahmanes déplacent ces disques conformément aux règles immuables de Brahma depuis cette époque. Le puzzle est donc également connu sous le nom de Tour de Brahma . Selon la légende, lorsque le dernier mouvement du puzzle sera terminé, le monde prendra fin.

Si la légende était vraie, et si les prêtres étaient capables de déplacer des disques à raison d'un disque par seconde, en utilisant le plus petit nombre de mouvements, cela leur prendrait 2 64  − 1 secondes ou environ 585 milliards d' années pour terminer, ce qui représente environ 42 fois l'âge actuel de l'univers.

Il existe de nombreuses variantes de cette légende. Par exemple, dans certains récits, le temple est un monastère et les prêtres sont des moines . Le temple ou le monastère peut se trouver dans divers endroits, dont Hanoï , et peut être associé à n'importe quelle religion . Dans certaines versions, d'autres éléments sont introduits, comme le fait que la tour a été créée au début du monde, ou que les prêtres ou les moines ne peuvent effectuer qu'un seul mouvement par jour.

Solution

Le puzzle peut être joué avec n'importe quel nombre de disques, bien que de nombreuses versions de jouets en aient environ 7 à 9. Le nombre minimal de mouvements requis pour résoudre un puzzle de la Tour de Hanoï est de 2 n − 1 , où n est le nombre de disques. C'est précisément le n ème nombre de Mersenne sans exigence de primalité.

Solution itérative

Animation d'un algorithme itératif résolvant un problème à 6 disques

Une solution simple pour le puzzle jouet consiste à alterner les mouvements entre la plus petite pièce et une autre pièce. Lorsque vous déplacez la plus petite pièce, déplacez-la toujours vers la position suivante dans le même sens (vers la droite si le nombre de pièces de départ est pair, vers la gauche si le nombre de pièces de départ est impair). S'il n'y a pas de position de tour dans la direction choisie, déplacez la pièce vers l'extrémité opposée, mais continuez ensuite à vous déplacer dans la bonne direction. Par exemple, si vous avez commencé avec trois pièces, vous déplaceriez la plus petite pièce vers l'extrémité opposée, puis continuerez dans la direction de gauche après cela. Lorsque le tour est de déplacer la pièce non la plus petite, il n'y a qu'un seul mouvement légal. Faire cela terminera le puzzle en un minimum de mouvements.

Énoncé plus simple de la solution itérative

Pour un nombre pair de disques :

  • faire le mouvement légal entre les chevilles A et B (dans les deux sens),
  • faire le mouvement légal entre les chevilles A et C (dans les deux sens),
  • faire le mouvement légal entre les chevilles B et C (dans les deux sens),
  • répéter jusqu'à la fin.

Pour un nombre impair de disques :

  • faire le mouvement légal entre les chevilles A et C (dans les deux sens),
  • faire le mouvement légal entre les chevilles A et B (dans les deux sens),
  • faire le mouvement légal entre les chevilles B et C (dans les deux sens),
  • répéter jusqu'à la fin.

Dans chaque cas, un total de 2 n − 1 mouvements sont effectués.

Solution itérative équivalente

Une autre façon de générer la solution itérative optimale unique :

Numérotez les disques de 1 à n (du plus grand au plus petit).

  • Si n est impair, le premier mouvement est de la cheville A à la cheville C.
  • Si n est pair, le premier mouvement est de la cheville A à la cheville B.

Maintenant, ajoutez ces contraintes :

  • Aucun disque impair ne peut être placé directement sur un disque impair.
  • Aucun disque pair ne peut être placé directement sur un disque pair.
  • Il y aura parfois deux piquets possibles : l'un aura des disques, et l'autre sera vide. Placez le disque sur la cheville non vide.
  • Ne déplacez jamais un disque deux fois de suite.

Compte tenu de ces contraintes après le premier coup, il n'y a qu'un seul coup légal à chaque tour suivant.

La séquence de ces mouvements uniques est une solution optimale au problème équivalent à la solution itérative décrite ci-dessus.

Solution récursive

Illustration d'une solution récursive pour le puzzle des Tours de Hanoï avec 4 disques

La clé pour résoudre un problème est récursive de reconnaître qu'il peut être décomposé en une collection de sous-problèmes plus petits, à chacune desquelles cette même procédure de résolution générale que nous cherchons applique, et la solution totale est alors trouvée dans certains simples loin des solutions de ces sous-problèmes. Chacun de ces sous-problèmes créés étant "plus petit" garantit que le ou les cas de base seront finalement atteints. De là, pour les Tours de Hanoï :

  • étiquetez les chevilles A, B, C,
  • soit n le nombre total de disques,
  • numéroter les disques de 1 (le plus petit, le plus haut) à n (le plus grand, le plus bas).

En supposant que tous les n disques soient répartis selon des dispositions valides entre les chevilles ; en supposant qu'il y a m disques supérieurs sur une cheville source et que tous les autres disques sont plus grands que m , ils peuvent donc être ignorés en toute sécurité ; pour déplacer m disques d'un piquet source vers un piquet cible en utilisant un piquet de rechange , sans enfreindre les règles :

  1. Déplacez m − 1 disques de la source vers la cheville de rechange , par la même procédure de résolution générale . Les règles ne sont pas violées, par hypothèse. Cela laisse le disque m comme disque supérieur sur la cheville source.
  2. Déplacez le disque m de la source à la cheville cible , ce qui est garanti comme un mouvement valide, par les hypothèses - une étape simple .
  3. Déplacez les m − 1 disques que nous venons de placer sur le disque de secours, du disque de secours au piquet cible par la même procédure de résolution générale , afin qu'ils soient placés au-dessus du disque m sans enfreindre les règles.
  4. Le cas de base est de déplacer 0 disque (aux étapes 1 et 3), c'est-à-dire de ne rien faire – ce qui ne viole évidemment pas les règles.

La solution complète de la Tour de Hanoï consiste alors à déplacer n disques du piquet source A vers le piquet cible C, en utilisant B comme piquet de rechange.

Cette approche peut recevoir une preuve mathématique rigoureuse avec induction mathématique et est souvent utilisée comme exemple de récursivité lors de l'enseignement de la programmation.

Analyse logique de la solution récursive

Comme dans de nombreux puzzles mathématiques, trouver une solution est facilité en résolvant un problème un peu plus général : comment déplacer une tour de disques h (hauteur) d'une cheville de départ f = A (de) à une cheville de destination t = C (à ), B étant le troisième pion restant et en supposant que tf . Tout d'abord, remarquons que le problème est symétrique pour les permutations des noms des piquets ( groupe symétrique S 3 ). Si une solution est connue pour passer du piquet A au piquet C , alors, en renommant les piquets, la même solution peut être utilisée pour tout autre choix de piquet de départ et de destination. S'il n'y a qu'un seul disque (voire aucun), le problème est trivial. Si h = 1, alors déplacez simplement le disque de la cheville A à la cheville C . Si h > 1, alors quelque part le long de la séquence de mouvements, le plus grand disque doit être déplacé du piquet A vers un autre piquet, de préférence vers le piquet C . La seule situation qui permet ce déplacement est lorsque tous les disques h − 1 plus petits sont sur la cheville B . Par conséquent, tout d'abord tous les h − 1 disques plus petits doivent aller de A à B . Ensuite, déplacez le plus grand disque et enfin déplacez les h − 1 petits disques de la cheville B à la cheville C . La présence du plus gros disque n'empêche aucun déplacement des h − 1 plus petits disques et peut être temporairement ignorée. Maintenant, le problème se réduit à déplacer h − 1 disques d'un piquet à un autre, d'abord de A à B et ensuite de B à C , mais la même méthode peut être utilisée les deux fois en renommant les piquets. La même stratégie peut être utilisée pour réduire le problème h − 1 à h − 2, h − 3, et ainsi de suite jusqu'à ce qu'il ne reste qu'un seul disque. C'est ce qu'on appelle la récursivité. Cet algorithme peut être schématisé comme suit.

Identifiez les disques par ordre de taille croissante par les nombres naturels de 0 à h mais non compris . Par conséquent, le disque 0 est le plus petit et le disque h − 1 le plus grand.

Voici une procédure pour déplacer une tour de disques h d'un piquet A sur un piquet C , B étant le troisième piquet restant :

  1. Si h > 1, utilisez d'abord cette procédure pour déplacer les h − 1 disques plus petits de la cheville A à la cheville B .
  2. Maintenant, le plus grand disque, c'est-à-dire le disque h, peut être déplacé de la cheville A à la cheville C .
  3. Si h > 1, utilisez à nouveau cette procédure pour déplacer les h − 1 disques plus petits de la cheville B à la cheville C .

Au moyen de l'induction mathématique , il est facilement prouvé que la procédure ci-dessus nécessite le nombre minimal de coups possibles et que la solution produite est la seule avec ce nombre minimal de coups. A l'aide des relations de récurrence , le nombre exact de déplacements requis par cette solution peut être calculé par : . Ce résultat est obtenu en notant que les étapes 1 et 3 effectuent des mouvements et que l'étape 2 effectue un mouvement, ce qui donne .

Implémentation récursive

Le code Python suivant met en évidence une fonction essentielle de la solution récursive, qui pourrait autrement être mal comprise ou négligée. C'est-à-dire qu'à chaque niveau de récursivité, le premier appel récursif inverse les piles cible et auxiliaire , tandis que dans le deuxième appel récursif , les piles source et auxiliaire sont inversées.

A = [3, 2, 1]
B = []
C = []

def move(n, source, target, auxiliary):
    if n > 0:
        # Move n - 1 disks from source to auxiliary, so they are out of the way
        move(n - 1, source, auxiliary, target)

        # Move the nth disk from source to target
        target.append(source.pop())

        # Display our progress
        print(A, B, C, '##############', sep='\n')

        # Move the n - 1 disks that we left on auxiliary onto target
        move(n - 1, auxiliary, target, source)

# Initiate call from source A to target C with auxiliary B
move(3, A, C, B)

Solution non récursive

La liste des déplacements d'une tour transportée d'un piquet à un autre, telle que produite par l'algorithme récursif, présente de nombreuses régularités. Lorsque l'on compte les coups à partir de 1, l'ordinal du disque à déplacer pendant le coup m est le nombre de fois où m peut être divisé par 2. Par conséquent, chaque coup impair implique le plus petit disque. On peut également observer que le plus petit disque traverse les piquets f , t , r , f , t , r , etc. pour une hauteur impaire de la tour et traverse les piquets f , r , t , f , r , t , etc pour une hauteur uniforme de la tour. Ceci fournit l'algorithme suivant, qui est plus facile, réalisé à la main, que l'algorithme récursif.

En coups alternatifs :

  • Déplacez le plus petit disque vers la cheville d'où il n'est pas venu récemment.
  • Déplacez un autre disque légalement (il n'y aura qu'une seule possibilité).

Pour le tout premier coup, le plus petit disque va à la cheville t si h est impair et à la cheville r si h est pair.

Observez également que :

  • Les disques dont les ordinaux ont une parité paire se déplacent dans le même sens que le plus petit disque.
  • Les disques dont les ordinaux ont une parité impaire se déplacent en sens inverse.
  • Si h est pair, la troisième cheville restante lors des déplacements successifs est t , r , f , t , r , f , etc.
  • Si h est impair, la troisième cheville restante lors des déplacements successifs est r , t , f , r , t , f , etc.

Avec cette connaissance, un ensemble de disques au milieu d'une solution optimale peut être récupéré sans plus d'informations d'état que les positions de chaque disque :

  • Appelez les mouvements détaillés ci-dessus le mouvement "naturel" d'un disque.
  • Examinez le plus petit disque du haut qui n'est pas le disque 0, et notez quel serait son seul coup (légal) : s'il n'y a pas un tel disque, alors nous sommes soit au premier, soit au dernier coup.
  • Si ce mouvement est le mouvement "naturel" du disque, alors le disque n'a pas été déplacé depuis le dernier mouvement du disque 0, et ce mouvement doit être effectué.
  • Si ce mouvement n'est pas le mouvement "naturel" du disque, alors déplacez le disque 0.

Solution binaire

Les positions des disques peuvent être déterminées plus directement à partir de la représentation binaire (base 2) du numéro de coup (l'état initial étant le coup #0, avec tous les chiffres 0, et l'état final étant avec tous les chiffres 1), en utilisant les règles suivantes :

  • Il y a un chiffre binaire ( bit ) pour chaque disque.
  • Le bit le plus significatif (le plus à gauche) représente le plus gros disque. Une valeur de 0 indique que le plus gros disque est sur le piquet initial, tandis qu'un 1 indique qu'il est sur le piquet final (piquet de droite si le nombre de disques est impair et piquet du milieu sinon).
  • La chaîne de bits est lue de gauche à droite et chaque bit peut être utilisé pour déterminer l'emplacement du disque correspondant.
  • Un bit de même valeur que le précédent signifie que le disque correspondant est empilé au-dessus du disque précédent sur le même plot.
    (C'est-à-dire : une séquence droite de 1 ou de 0 signifie que les disques correspondants sont tous sur la même cheville.)
  • Un bit avec une valeur différente du précédent signifie que le disque correspondant est une position à gauche ou à droite du précédent. Que ce soit à gauche ou à droite est déterminé par cette règle :
    • Supposons que la cheville initiale est à gauche.
    • Supposons également "l'emballage" - donc la cheville droite compte comme une cheville "gauche" de la cheville gauche, et vice versa.
    • Soit n le nombre de disques plus grands qui sont situés sur la même cheville que leur premier plus grand disque et ajoutez 1 si le plus grand disque est sur la cheville gauche. Si n est pair, le disque est situé un piquet à droite, si n est impair, le disque est situé un piquet à gauche (en cas de nombre pair de disques et vice versa sinon).

Par exemple, dans un Hanoi à 8 disques :

  • Déplacer 0 = 00000000.
    • Le plus grand disque est 0, il se trouve donc sur la cheville gauche (initiale).
    • Tous les autres disques sont également à 0, ils sont donc empilés dessus. Par conséquent, tous les disques sont sur la cheville initiale.
  • Déplacer 2 8 − 1 = 11111111.
    • Le plus grand disque est 1, il se trouve donc sur la cheville centrale (finale).
    • Tous les autres disques ont également la valeur 1, ils sont donc empilés dessus. Par conséquent, tous les disques sont sur la cheville finale et le puzzle est terminé.
  • Déplacez 216 10 = 11011000.
    • Le plus grand disque est 1, il se trouve donc sur la cheville centrale (finale).
    • Le disque deux est également 1, il est donc empilé dessus, sur la cheville du milieu.
    • Le disque trois vaut 0, il est donc sur un autre piquet. Puisque n est impair ( n = 1), c'est un piquet vers la gauche, c'est-à-dire sur le piquet gauche.
    • Le disque quatre est 1, il est donc sur une autre cheville. Puisque n est impair ( n = 1), c'est un piquet à gauche, c'est-à-dire sur le piquet de droite.
    • Le disque cinq est également 1, il est donc empilé dessus, sur la cheville droite.
    • Le disque six vaut 0, il est donc sur un autre piquet. Puisque n est pair ( n = 2), le disque est un piquet vers la droite, c'est-à-dire sur le piquet gauche.
    • Les disques sept et huit sont également à 0, ils sont donc empilés dessus, sur la cheville gauche.

Les chevilles source et destination pour le m ème mouvement peuvent également être trouvées élégamment à partir de la représentation binaire de m en utilisant des opérations au niveau du bit . Pour utiliser la syntaxe du langage de programmation C , le déplacement m est de peg (m & m - 1) % 3to peg ((m | m - 1) + 1) % 3, où les disques commencent sur le peg 0 et finissent sur le peg 1 ou 2 selon que le nombre de disques est pair ou impair. Une autre formulation est de cheville (m - (m & -m)) % 3à cheville (m + (m & -m)) % 3.

De plus, le disque à déplacer est déterminé par le nombre de fois que le nombre de déplacements ( m ) peut être divisé par 2 (c'est-à-dire le nombre de bits zéro à droite), en comptant le premier déplacement comme 1 et en identifiant les disques par les numéros 0, 1, 2, etc. par ordre de taille croissante. Cela permet à une implémentation informatique non récursive très rapide de trouver les positions des disques après m déplacements sans référence à un quelconque déplacement ou distribution de disques antérieurs.

L'opération, qui compte le nombre de zéros consécutifs à la fin d'un nombre binaire, donne une solution simple au problème : les disques sont numérotés à partir de zéro, et au déplacement m , le nombre de disques compte les zéros de fuite est déplacé de la distance minimale possible à la droite (en tournant vers la gauche au besoin).

Solution de code Gray

Le système de numération binaire des codes Gray offre une autre façon de résoudre le puzzle. Dans le système Gray, les nombres sont exprimés dans une combinaison binaire de 0 et de 1, mais plutôt que d'être un système de numération positionnelle standard , le code Gray part du principe que chaque valeur diffère de son prédécesseur par un seul (et exactement un) bit modifié .

Si l'on compte en code Gray d'une taille en bits égale au nombre de disques dans une tour particulière de Hanoï, commence à zéro et compte vers le haut, alors le bit changé à chaque mouvement correspond au disque à déplacer, où le bit le moins significatif est le plus petit disque, et le bit le plus significatif est le plus gros.

En comptant les déplacements à partir de 1 et en identifiant les disques par des nombres commençant à 0 par ordre de taille croissante, l'ordinal du disque à déplacer lors du déplacement m est le nombre de fois que m peut être divisé par 2.

Cette technique identifie le disque à déplacer, mais pas vers où le déplacer. Pour le plus petit disque, il y a toujours deux possibilités. Pour les autres disques il y a toujours une possibilité, sauf lorsque tous les disques sont sur le même piquet, mais dans ce cas soit c'est le plus petit disque qu'il faut déplacer, soit l'objectif est déjà atteint. Heureusement, il existe une règle qui indique où déplacer le plus petit disque. Soit f la cheville de départ, t la cheville de destination et r la troisième cheville restante. Si le nombre de disques est impair, le plus petit disque parcourt les piquets dans l'ordre ftrftr , etc. Si le nombre de disques est pair, il faut inverser : frtfrt , etc.

La position du changement de bit dans la solution du code Gray donne la taille du disque déplacé à chaque pas : 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, ... (séquence A001511 dans l' OEIS ), une séquence également connue sous le nom de fonction de règle , ou une de plus que la puissance 2 dans le numéro de coup. En Wolfram Language , IntegerExponent[Range[2^8 - 1], 2] + 1donne des mouvements pour le puzzle à 8 disques.

Représentation graphique

Le jeu peut être représenté par un graphe non orienté , les nœuds représentant les distributions de disques et les arêtes représentant les déplacements. Pour un disque, le graphe est un triangle :

Tour de hanoi graph.svg

Le graphique pour deux disques est constitué de trois triangles connectés pour former les coins d'un triangle plus grand.

Une deuxième lettre est ajoutée pour représenter le plus grand disque. Il est clair qu'il ne peut pas être déplacé dans un premier temps.

Le petit triangle le plus haut représente maintenant les possibilités d'un coup avec deux disques :

Tour de hanoi graph.svg

Les nœuds aux sommets du triangle le plus à l'extérieur représentent des distributions avec tous les disques sur la même cheville.

Pour h + 1 disques, prenez le graphe de h disques et remplacez chaque petit triangle par le graphe de deux disques.

Pour trois disques, le graphe est :

Tour de hanoi graph.svg
Le graphique du jeu du niveau 7 montre la parenté avec le triangle de Sierpiński .
  • appeler les chevilles a, b et c
  • liste les positions des disques de gauche à droite par ordre de taille croissante

Les côtés du triangle le plus à l'extérieur représentent les chemins les plus courts pour déplacer une tour d'un piquet à un autre. Le bord au milieu des côtés du plus grand triangle représente un mouvement du plus grand disque. Le bord au milieu des côtés de chaque triangle plus petit suivant représente un mouvement de chaque disque plus petit suivant. Les côtés des plus petits triangles représentent les mouvements du plus petit disque.

En général, pour un puzzle à n disques, il y a 3 n nœuds dans le graphe ; chaque nœud a trois arêtes vers d'autres nœuds, sauf les trois nœuds d'angle qui en ont deux : il est toujours possible de déplacer le plus petit disque vers l'un des deux autres piquets, et il est possible de déplacer un disque entre ces deux piquets sauf dans la situation où tous les disques sont empilés sur une seule cheville. Les nœuds d'angle représentent les trois cas où tous les disques sont empilés sur une seule cheville. Le diagramme pour n  + 1 disques est obtenu en prenant trois copies du diagramme des n disques - chacune représentant tous les états et mouvements des plus petits disques pour une position particulière du nouveau plus grand disque - et en les joignant aux coins avec trois de nouveaux bords, représentant les trois seules possibilités de déplacer le plus gros disque. La figure résultante a donc 3 n +1 nœuds et a encore trois coins restants avec seulement deux arêtes.

Au fur et à mesure que d'autres disques sont ajoutés, la représentation graphique du jeu ressemblera à une figure fractale , le triangle de Sierpiński . Il est clair que la grande majorité des positions du puzzle ne sera jamais atteinte en utilisant la solution la plus courte possible ; en effet, si les prêtres de la légende utilisent la solution la plus longue possible (sans revisiter aucun poste), il leur faudra 3 64  − 1 déplacements, soit plus de 10 23 ans.

Le chemin non répétitif le plus long pour trois disques peut être visualisé en effaçant les bords inutilisés :

Tour de hanoi graph.svg

Incidemment, ce chemin non répétitif le plus long peut être obtenu en interdisant tout déplacement de a à c .

Le cycle hamiltonien pour trois disques est :

Tour de hanoi graph.svg

Les graphiques montrent clairement que :

  • A partir de chaque distribution arbitraire de disques, il existe exactement un moyen le plus court de déplacer tous les disques sur l'un des trois rattachements.
  • Entre chaque paire de distributions arbitraires de disques, il existe un ou deux chemins différents les plus courts.
  • À partir de chaque distribution arbitraire de disques, il existe un ou deux chemins différents les plus longs qui ne se croisent pas pour déplacer tous les disques vers l'un des trois piquets.
  • Entre chaque paire de distributions arbitraires de disques, il y a un ou deux chemins différents les plus longs qui ne se croisent pas.
  • Soit N h le nombre de chemins non auto-croisés pour déplacer une tour de h disques d'un piquet à un autre. Puis:
    • N 1 = 2
    • N h +1 = ( N h ) 2 + ( N h ) 3

Cela donne N h à 2, 12, 1872, 6563711232, ... (séquence A125295 dans l' OEIS )

Variantes

Chevilles adjacentes

Si tous les déplacements doivent se faire entre des piquets adjacents (c'est-à-dire étant donné les piquets A, B, C, on ne peut pas se déplacer directement entre les piquets A et C), alors déplacer une pile de n disques du piquet A au piquet C prend 3 n − 1 coups. La solution utilise les 3 n positions valides, prenant toujours le coup unique qui n'annule pas le coup précédent. La position avec tous les disques à la cheville B est atteinte à mi-chemin, c'est-à-dire après (3 n − 1) / 2 coups.

Hanoï cyclique

Dans Hanoi cyclique, on nous donne trois piquets (A, B, C), qui sont disposés en cercle, les sens horaire et antihoraire étant définis respectivement comme A - B - C - A et A - C - B - A. Le sens de déplacement du disque doit être dans le sens des aiguilles d'une montre. Il suffit de représenter la séquence de disques à déplacer. La solution peut être trouvée en utilisant deux procédures mutuellement récursives :

Pour déplacer n disques dans le sens inverse des aiguilles d'une montre vers le piquet cible voisin :

  1. déplacer n − 1 disques dans le sens inverse des aiguilles d'une montre jusqu'à la cheville cible
  2. déplacer le disque # n d' un pas dans le sens des aiguilles d'une montre
  3. déplacer n − 1 disques dans le sens des aiguilles d' une montre jusqu'à la cheville de départ
  4. déplacer le disque # n d' un pas dans le sens des aiguilles d'une montre
  5. déplacer n − 1 disques dans le sens inverse des aiguilles d'une montre jusqu'à la cheville cible

Pour déplacer n disques dans le sens des aiguilles d' une montre vers le piquet cible voisin :

  1. déplacer n − 1 disques dans le sens inverse des aiguilles d'une montre vers une cheville de rechange
  2. déplacer le disque # n d' un pas dans le sens des aiguilles d'une montre
  3. déplacer n − 1 disques dans le sens inverse des aiguilles d'une montre jusqu'à la cheville cible

Soit C(n) et A(n) représentant n disques en mouvement dans le sens horaire et antihoraire, alors nous pouvons écrire les deux formules :

      C(n) = A(n-1) n A(n-1)    and      A(n) = A(n-1) n C(n-1) n A(n-1).
Thus  C(1) = 1                  and      A(1) = 1 1,
      C(2) = 1 1 2 1 1          and      A(2) = 1 1 2 1 2 1 1.

La solution pour le Hanoi cyclique a quelques propriétés intéressantes :

1) Les mouvements de transfert d'une tour de disques d'une cheville à une autre cheville sont symétriques par rapport aux points centraux.

2) Le plus petit disque est le premier et le dernier disque à déplacer.

3) Les groupes des plus petits mouvements de disque alternent avec des mouvements simples d'autres disques.

4) Le nombre de déplacements de disques spécifié par C(n) et A(n) est minimal.

Avec quatre chevilles et au-delà

Bien que la version à trois chevilles ait une solution récursive simple connue depuis longtemps, la solution optimale pour le problème de la tour de Hanoï à quatre chevilles (appelée puzzle de Reve) n'a été vérifiée qu'en 2014, par Bousch.

Cependant, dans le cas de quatre chevilles ou plus, l'algorithme Frame-Stewart est connu sans preuve d'optimalité depuis 1941.

Pour la dérivation formelle du nombre exact de mouvements minimaux requis pour résoudre le problème en appliquant l'algorithme Frame-Stewart (et d'autres méthodes équivalentes), voir l'article suivant.

Pour d'autres variantes du problème de la tour à quatre chevilles de Hanoï, voir le document d'enquête de Paul Stockmeyer.

Les configurations de jeu dites Towers of Bucarest et Towers of Klagenfurt produisent des codes Gray ternaires et pentanaires.

Algorithme Frame–Stewart

L'algorithme Frame-Stewart est décrit ci-dessous :

  • Soit le nombre de disques.
  • Soit le nombre de chevilles.
  • Définir comme étant le nombre minimum de déplacements requis pour transférer n disques à l'aide de r chevilles.

L'algorithme peut être décrit récursivement :

  1. Pour certains , , transférez les disques supérieurs sur un seul piquet autre que les piquets de départ ou de destination, en prenant des mouvements.
  2. Sans perturber le piquet qui contient maintenant les disques supérieurs , transférez les disques restants vers le piquet de destination, en utilisant uniquement les piquets restants , en effectuant des mouvements.
  3. Enfin, transférez les disques supérieurs vers la cheville de destination, en effectuant des mouvements.

L'ensemble du processus prend des mouvements. Par conséquent, le compte doit être sélectionné pour lequel cette quantité est minimale. Dans le cas à 4 chevilles, l'optimal est égal à , où est la fonction entière la plus proche . Par exemple, dans le cours UPenn CIS 194 sur Haskell, la première page de devoir répertorie la solution optimale pour le cas à 15 disques et à 4 chevilles en 129 étapes, qui est obtenue pour la valeur ci-dessus de k .

Cet algorithme est supposé être optimal pour un nombre quelconque de chevilles ; son nombre de coups est de 2 Θ ( n 1/( r −2) ) (pour r fixe ).

Les plus courts chemins généraux et le nombre 466/885

Une curieuse généralisation du but initial du puzzle est de partir d'une configuration donnée des disques où tous les disques ne sont pas forcément sur le même piquet et d'arriver en un nombre minimal de coups à une autre configuration donnée. En général, il peut être assez difficile de calculer une séquence de mouvements la plus courte pour résoudre ce problème. Une solution a été proposée par Andreas Hinz et est basée sur l'observation que dans une séquence de mouvements la plus courte, le plus gros disque qui doit être déplacé (évidemment on peut ignorer tous les plus gros disques qui occuperont la même cheville à la fois dans le configurations finales) se déplacera soit exactement une fois, soit exactement deux fois.

Les mathématiques liées à ce problème généralisé deviennent encore plus intéressantes lorsque l'on considère le nombre moyen de mouvements dans une séquence de mouvements la plus courte entre deux configurations de disque initiale et finale choisies au hasard. Hinz et Chan Tat-Hung ont découvert indépendamment (voir aussi ) que le nombre moyen de mouvements dans une tour à n disques est donné par la formule exacte suivante :

Pour n suffisamment grand , seuls les premier et deuxième termes ne convergent pas vers zéro, nous obtenons donc une expression asymptotique : , as . Ainsi intuitivement, on pourrait interpréter la fraction de comme représentant le rapport du travail que l'on doit effectuer pour passer d'une configuration choisie au hasard à une autre configuration choisie au hasard, par rapport à la difficulté d'avoir à franchir le chemin de longueur "le plus difficile" qui consiste à déplacer tous les disques d'un piquet à un autre. Une autre explication de l'apparition de la constante 466/885, ainsi qu'un nouvel algorithme quelque peu amélioré pour le calcul du chemin le plus court, ont été donnés par Romik.

Hanoï magnétique

Dans la tour magnétique de Hanoï, chaque disque a deux faces distinctes Nord et Sud (typiquement colorées "rouge" et "bleu"). Les disques ne doivent pas être placés avec les pôles similaires ensemble - des aimants dans chaque disque empêchent ce mouvement illégal. De plus, chaque disque doit être retourné lorsqu'il est déplacé.

Configuration initiale des Tours bicolores de Hanoï (n=4)

Tours bicolores de Hanoï

Cette variante du célèbre puzzle de la Tour de Hanoï a été proposée aux élèves de la 3e à la 6e année au 2e Championnat de France des Jeux Mathématiques et Logiques qui s'est tenu en juillet 1988.

Configuration finale des Tours bicolores de Hanoï (n=4)

Les règles du puzzle sont essentiellement les mêmes : les disques sont transférés entre les chevilles un à la fois. A aucun moment, un plus gros disque ne peut être placé sur un plus petit. La différence est que maintenant, pour chaque taille, il y a deux disques : un noir et un blanc. Aussi, il y a maintenant deux tours de disques de couleurs alternées. Le but du puzzle est de rendre les tours monochromes (même couleur). Les plus gros disques au bas des tours sont supposés changer de position.

Tour d'Hanoy

Une variante du puzzle a été adaptée en un jeu de solitaire avec neuf cartes à jouer sous le nom de Tower of Hanoy . On ne sait pas si l'orthographe modifiée du nom d'origine est délibérée ou accidentelle.

Applications

Image topographique AFM 3D d'une nanofeuille de palladium multicouche sur une plaquette de silicium, avec une structure de type Tour de Hanoï.

La tour de Hanoï est fréquemment utilisée dans les recherches psychologiques sur la résolution de problèmes . Il existe également une variante de cette tâche appelée Tour de Londres pour le diagnostic neuropsychologique et le traitement des fonctions exécutives.

Zhang et Norman ont utilisé plusieurs représentations isomorphes (équivalentes) du jeu pour étudier l'impact de l'effet de représentation dans la conception des tâches. Ils ont démontré un impact sur les performances des utilisateurs en modifiant la façon dont les règles du jeu sont représentées, en utilisant des variations dans la conception physique des composants du jeu. Cette connaissance a eu un impact sur le développement du cadre TURF pour la représentation de l'interaction homme-machine .

La tour de Hanoï est également utilisée comme schéma de rotation des sauvegardes lors de l'exécution de sauvegardes de données informatiques impliquant plusieurs bandes/supports.

Comme mentionné ci-dessus, la Tour de Hanoï est populaire pour enseigner les algorithmes récursifs aux étudiants débutants en programmation. Une version illustrée de ce puzzle est programmée dans l' éditeur emacs , accessible en tapant Mx hanoi. Il existe également un exemple d'algorithme écrit en Prolog .

La tour de Hanoï est également utilisée comme test par les neuropsychologues essayant d'évaluer les déficits du lobe frontal .

En 2010, les chercheurs ont publié les résultats d'une expérience qui a révélé que l'espèce de fourmis Linepithema humile était capable de résoudre avec succès la version à 3 disques du problème de la tour de Hanoï grâce à la dynamique non linéaire et aux signaux de phéromone.

En 2014, les scientifiques ont synthétisé des nanofeuillets de palladium multicouches avec une structure semblable à la tour de Hanoï.

Dans la culture populaire

Dans l'histoire de science-fiction "Now Inhale", d' Eric Frank Russell , un humain est retenu prisonnier sur une planète où la coutume locale est de faire jouer le prisonnier à un jeu jusqu'à ce qu'il soit gagné ou perdu avant son exécution. Le protagoniste sait qu'un navire de sauvetage peut mettre un an ou plus à arriver, il choisit donc de jouer à Towers of Hanoi avec 64 disques. Cette histoire fait référence à la légende des moines bouddhistes jouant le jeu jusqu'à la fin du monde.

Dans l' histoire de Doctor Who The Celestial Toymaker de 1966 , le méchant éponyme oblige le Docteur à jouer à un jeu de dix pièces de la Tour de Hanoï de 1023 coups intitulé The Trilogic Game avec les pièces formant une forme de pyramide lorsqu'elles sont empilées.

En 2007, le concept du problème des tours de Hanoï a été utilisé dans le professeur Layton et la boîte diabolique dans les puzzles 6, 83 et 84, mais les disques avaient été changés en crêpes. Le puzzle était basé sur un dilemme où le chef d'un restaurant devait déplacer un tas de crêpes d'une assiette à l'autre avec les principes de base du puzzle original (c'est-à-dire trois assiettes sur lesquelles les crêpes pouvaient être déplacées, ne pouvant mettre une plus grosse crêpe sur une plus petite, etc.)

Dans le film L' ascension de la planète des singes (2011), ce puzzle, appelé dans le film la "Tour Lucas", sert de test pour étudier l'intelligence des singes.

Le puzzle est régulièrement présenté dans les jeux d' aventure et de puzzle . Puisqu'il est facile à mettre en œuvre et facilement reconnaissable, il convient parfaitement à une utilisation comme puzzle dans un jeu graphique plus vaste (par exemple Star Wars : Knights of the Old Republic et Mass Effect ). Certaines implémentations utilisent des disques droits, mais d'autres déguisent le puzzle sous une autre forme. Il existe une version arcade de Sega .

Une version à 15 disques du puzzle apparaît dans le jeu Sunless Sea comme un verrou vers une tombe. Le joueur a la possibilité de cliquer sur chaque mouvement du puzzle afin de le résoudre, mais le jeu note qu'il faudra 32767 mouvements pour terminer. Si un joueur particulièrement dévoué clique jusqu'à la fin du puzzle, il est révélé que terminer le puzzle ne déverrouille pas la porte.

Dans Yu-Gi-Oh! VRAINS , un groupe de hackers appelé « Knight of Hanoi » crée une structure nommée « Tower of Hanoi » au sein du réseau de réalité virtuelle éponyme VRAINS.

Cela a été utilisé pour la première fois comme un défi à Survivor Thailand en 2002, mais plutôt que des bagues, les pièces ont été conçues pour ressembler à un temple. Sook Jai a lancé le défi de se débarrasser de Jed même si Shii-Ann savait très bien comment terminer le puzzle. Le problème est présenté dans le cadre d'un défi de récompense dans un épisode de 2011 de la version américaine de la série télévisée Survivor . Les deux joueurs ( Ozzy Lusth et Benjamin "Coach" Wade ) ont eu du mal à comprendre comment résoudre l'énigme et sont aidés par les autres membres de la tribu.

Voir également

Remarques

Liens externes