Les tours de Hanoï

Claus de Siam a vu, dans ses voyages pour la publication des écrits de l'illustre Fer-Fer-Tam-Tam, dans le grand temple de Bénarès, au-dessous du dôme qui marque le centre du monde, trois aiguilles de diamant, plantées dans une dalle d'airain, hautes d'une coudée et grosses comme le corps d'une abeille. Sur une de ces aiguilles, Dieu enfila au commencement des siècles, 64 disques d'or pur, le plus large reposant sur l'airain, et les autres, de plus en plus étroits, superposés jusqu'au sommet. C'est la tour sacrée du Brahmâ. Nuit et jour, les prêtres se succèdent sur les marches de l'autel, occupés à transporter la tour de la première aiguille sur la troisième, sans s'écarter des règles fixes que nous venons d'indiquer, et qui ont été imposées par Brahma. Quand tout sera fini, la tour et les brahmes tomberont, et ce sera la fin des mondes !

Présentation du problème

Règle du jeu

Le problème des tours de Hanoï est un problème récréatif inventé par Édouard Lucas en 1883. Le jeu est constitué de trois piliers, sur lesquels s’empilent un nombre \(n\) de disques (la "difficulté" du problème). Initialement, tous les disques sont placés sur le premier pilier.

Le but du jeu est de déplacer la pyramide de disques du pilier \(A\) au pilier \(C\) en respectant les règles suivantes :

• on ne peut déplacer qu'un seul disque à la fois ;
• lorsque l'on déplace un disque, on ne peut déplacer que le disque présent au sommet d'une pile ;
• lorsque l'on déplace un disque, on ne peut empiler un disque sur un disque de diamètre inférieur.

Notation

Pour noter les déplacements au cours d'une partie, on utilise la convention suivante : lorsque \(X\) et \(Y\) sont deux piliers différents parmi les piliers \(A\), \(B\) et \(C\), \(X \rightarrow Y\) indique que l'on a déplacé le disque au sommet du pilier \(A\) vers le pilier \(B\).

On considère la situation initiale suivante :

Indiquer la situation finale après les coups \(B \rightarrow A\), \(C \rightarrow B\), et \(C \rightarrow A\).

Résolution du problème

Une méthode naïve

Résoudre le problème des tours de Hanoï, successivement pour les difficultés 1, 2, 3, 4, et 5. Noter le nombre de coups réalisés pour résoudre le problème : compléter le tableau ci-dessous.

Difficulté	0	1	2	3	4	5
Nombre de coups

Une méthode magique

1. Compléter le tableau ci-dessous avec la liste des coups permettant de déplacer 3 disques du pilier \(X\) vers le pilier \(Y\), où \(X\) et \(Y\) appartiennent à \(\{A, B, C\}\).

   De A vers B	De A vers C	De B vers A	De B vers C	De C vers A	De C vers B
   \(A \rightarrow B\)		\(B \rightarrow A\)	\(B \rightarrow C\)	\(C \rightarrow A\)
   \(A \rightarrow C\)		\(B \rightarrow C\)	\(B \rightarrow A\)	\(C \rightarrow B\)
   \(B \rightarrow C\)		\(A \rightarrow C\)	\(C \rightarrow A\)	\(A \rightarrow B\)
   \(A \rightarrow B\)		\(B \rightarrow A\)	\(B \rightarrow C\)	\(C \rightarrow A\)
   \(C \rightarrow A\)		\(C \rightarrow B\)	\(A \rightarrow B\)	\(B \rightarrow C\)
   \(C \rightarrow B\)		\(C \rightarrow A\)	\(A \rightarrow C\)	\(B \rightarrow A\)
   \(A \rightarrow B\)		\(B \rightarrow A\)	\(B \rightarrow C\)	\(C \rightarrow A\)

2. En déduire, sans manipulation supplémentaire mais en réutilisant les cases du tableau précédent, la liste des coups permettant de déplacer 4 disques du pilier \(A\) vers le pilier \(C\).

En vous inspirant de la méthode de la question précédente, expliquer en français comment vous feriez pour résoudre le problème Hanoï de difficulté 5.

Comment feriez-vous pour résoudre le problème de Hanoï de difficulté 6 ?

Appeler le professeur avant de passer à la suite.

depart et arrivee sont deux caractères parmi 'A' 'B' et 'C'. On suppose écrite une fonction hanoi3 qui étant donné deux arguments depart et arrivee (supposés distincts), affiche la liste des déplacement permettant de déplacer 3 disques depuis le pilier depart vers le pilier arrivee. On suppose également écrite une fonction autre qui étant donné deux caractères distincts parmi 'A', 'B' et 'C', renvoie le troisième.

print(autre('A', 'B'))    
print(autre('C', 'A'))    

C
B

1. Écrire une fonction hanoi4 qui étant donné deux arguments depart et arrivee (supposés distincts), affiche la liste des déplacement permettant de déplacer 4 disques depuis le pilier depart vers le pilier arrivee.
2. Écrire une fonction hanoi5 qui étant donné deux arguments depart et arrivee (supposés distincts), affiche la liste des déplacement permettant de déplacer 5 disques depuis le pilier depart vers le pilier arrivee.

Écrire une fonction hanoi qui prend en argument un entier n (le nombre de disques), et deux caractères depart et arrivee (supposés distincts parmi 'A'​, 'B' et 'C') et qui affiche la liste des déplacements à effectuer pour déplacer n disques depuis le pilier depart vers le pilier arrivee.