Les Tours de Hanoï
« Les tours de Hanoï » est un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à déplacer 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 ceci en un minimum de coups, tout en respectant les règles suivantes :
- on ne peut déplacer qu’un seul disque à la fois ;
- on ne peut pas placer un disque au dessus d’un disque plus petit.
On suppose que cette dernière règle est également respectée dans la configuration de départ.
Classe principale du jeu
Le jeu des tours de Hanoï est défini par la classe Jeu_Hanoi
suivante :
class Jeu_Hanoi: def __init__(self, nbr_disq = 6): self.n = nbr_disq self.A = Pile() self.B = Pile() self.C = Pile() # Remplissage initial de la première pile for d in range(self.n): self.A.push(self.n-d)
Affichage
d’un disque
La fonction ch_dsq(n)
doit permettre de générer une chaîne de caractères représentant un disque de taille n
(1 < n < nombre de disques dans le jeu). La longueur de cette chaîne ne dépend que du nombre de disques du jeu.
Exemples , pour un jeu à 6 disques :
-
ch_dsq(4)
→" ****|**** "
ch_dsq(0)
→" | "
ch_dsq(n)
. (il pourra être nécessaire de la tester en dehors de la méthode __repr__()
)
d’une tour
La fonction ch_tour(t)
permet de générer une liste de chaînes de caractères représentant l’ensemble des disques présents sur la tour t
. La taille de de cette liste doit être toujours égale au nombre de disques du jeu.
Exemple pour une tour de 4 disques dans un jeu à 6 disques :
[" | ", " | ", " *|* ", " ***|*** ", " ****|**** ", "******|******"]
ch_tour(t)
permettant de générer une liste de lignes de texte représentant l’ensemble des disques fichés sur la tour t
.
Déplacement
La méthode get_tour
attend un seul argument (de type str
, valant 'A'
, 'B'
ou 'C'
) désignant une des tours du jeu et renvoie l’attribut A
, B
ou C
de l’objet de type Jeu_Hanoi
(de type Pile
).
Jeu_Hanoi
, une méthode deplacer
, qui attend deux arguments de type str
désignant deux des tours du jeu, et déplace le disque depuis la tour de « départ » (1er argument de la méthode) jusqu’à la tour d' »arrivée » (2ème argument de la méthode).Remarque : inutile de vérifier si la pile de départ est vide ou pas
Résolution du jeu
La résolution du jeu peut se faire de façon extrêmement simple … si l’on parvient à identifier la récursivité de la méthode :
Déplacer une pile de n disques depuis une tour de départ vers une tour d’arrivée en utilisant une tour libre (opération que l’on n’a pas le droit de faire en une seule étape) :
Revient à :
- déplacer une pile de n-1 disques depuis une tour de départ vers une tour libre (opération que l’on n’a pas le droit de faire en une seule étape) :
- déplacer le disque restant (depuis la tour de départ) vers la tour d’arrivée (opération autorisée !) :
- et enfin re-déplacer la pile de n-1 disques depuis la tour initialement libre (et qui le redevient !) vers la tour d’arrivée (opération que l’on n’a pas le droit de faire en une seule étape) :
hanoi(j, n, d, a, l)
, sous forme récursive qui résout le jeu j
(type Jeu_Hanoi
) , ce qui revient à déplacer n
disques (de type int
) depuis une tour de départ d
(type str
) vers une tour d’arrivée a
(type str
) en utilisant une tour libre l
(type str
).