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)

#!/usr/bin/env python
# -*- coding: utf-8 -*-

################################################################################
class Pile:
    def __init__(self):
        self.l = []

    def est_vide(self):
        return len(self.l) == 0

    def pop(self):
        return self.l.pop(0)

    def push(self, n):
        self.l = [n] + self.l


################################################################################
################################################################################
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)

    def __repr__(self):
        def ch_dsq(n):
            s = ""
            # ??????
            return s

        def ch_tour(t):
            l = []
            p = Pile()
            while not t.est_vide():
                n = t.pop()
                l.append(ch_dsq(n))
                p.push(n)
            # ??????
            return l

        L = []
        for tour in [self.A, self.B, self.C]:
            L.append(ch_tour(tour))

        ch = ""
        for d in range(self.n):
            ch += L[0][d] + L[1][d] + L[2][d] + "\n"
        return ch


    def get_tour(self, nom):
        """ Renvoie la Pile nommée nom (type str)
                exemple : 'A' --> self.A
        """
        if nom == 'A':
            return self.A
        elif nom == 'B':
            return self.B
        elif nom == 'C':
            return self.C


def hanoi(j, n, d, a, l):
    pass
    # ?????


if __name__ == "__main__":
    j = Jeu_Hanoi()
    hanoi(j, j.n, 'A', 'C', 'B')

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)→ "      |      "

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 :

 ["      |      ", "      |      ", "     *|*     ", "   ***|***   ", "  ****|****  ", "******|******"]

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).

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) :