Résolution des Tours de Hanoï en Python

La programmation du jeu de puzzle des tours de Hanoï est un excellent moyen de comprendre les concepts fondamentaux de la récursivité et de la programmation orientée objet. Le jeu des tours de Hanoï consiste à déplacer un ensemble de disques de tailles différentes d’une tour de départ à une tour d’arrivée en utilisant une tour intermédiaire, tout en respectant une règle simple : on ne peut déplacer qu’un seul disque à la fois et un disque plus grand ne peut jamais être placé sur un disque plus petit.

Pour programmer ce jeu en Python, nous pouvons utiliser la récursivité pour résoudre le problème de manière élégante. Voici une implémentation possible :

pythonCopy code
class TourDeHanoi:
    def __init__(self, nb_disques):
        self.nb_disques = nb_disques
        self.tours = {'A': [], 'B': [], 'C': []}
        self.initialiser_tour()

    def initialiser_tour(self):
        self.tours['A'] = list(range(self.nb_disques, 0, -1))

    def deplacer_disque(self, tour_depart, tour_arrivee):
        disque = self.tours[tour_depart].pop()
        self.tours[tour_arrivee].append(disque)
        print(f'Déplacer disque {disque} de {tour_depart} à {tour_arrivee}')

    def resoudre(self, n, depart='A', arrivee='C', intermediaire='B'):
        if n == 1:
            self.deplacer_disque(depart, arrivee)
        else:
            self.resoudre(n-1, depart, intermediaire, arrivee)
            self.deplacer_disque(depart, arrivee)
            self.resoudre(n-1, intermediaire, arrivee, depart)

if __name__ == '__main__':
    nb_disques = int(input("Entrez le nombre de disques : "))
    jeu = TourDeHanoi(nb_disques)
    jeu.resoudre(nb_disques)

Cette implémentation crée une classe TourDeHanoi qui représente le jeu. La méthode initialiser_tour initialise la tour de départ avec le nombre spécifié de disques. La méthode deplacer_disque permet de déplacer un disque d’une tour à une autre. La méthode resoudre est la fonction récursive principale qui résout le puzzle en déplaçant les disques de la tour de départ à la tour d’arrivée en utilisant la tour intermédiaire.

Lorsque vous exécutez ce code, il vous demande d’entrer le nombre de disques que vous souhaitez utiliser, puis il affiche les étapes pour résoudre le puzzle en déplaçant les disques de la tour A à la tour C en utilisant la tour B comme intermédiaire.

C’est une excellente façon d’apprendre les bases de la programmation en Python tout en s’amusant avec un jeu de puzzle classique comme les tours de Hanoï.

Le jeu des tours de Hanoï est un puzzle mathématique et logique qui a été inventé par le mathématicien français Édouard Lucas en 1883. Il tire son nom de la ville de Hanoï, au Vietnam, bien que son invention ne soit pas directement liée à cette ville.

Le puzzle consiste en trois tours et un certain nombre de disques de diamètres différents qui peuvent être empilés sur ces tours. Initialement, tous les disques sont empilés dans l’ordre décroissant de taille sur l’une des tours, avec le plus grand disque en bas et le plus petit en haut. Le but du jeu est de déplacer l’ensemble des disques de la tour de départ à la tour d’arrivée, en utilisant la troisième tour comme tour intermédiaire, tout en suivant deux règles simples :

1. Vous ne pouvez déplacer qu’un seul disque à la fois.
2. Un disque plus grand ne peut jamais être placé sur un disque plus petit.

La résolution du puzzle des tours de Hanoï peut sembler simple au premier abord, mais elle pose un défi intéressant en raison de sa nature récursive. Pour résoudre le puzzle, on peut utiliser une approche récursive, où l’on déplace un sous-ensemble de disques de la tour de départ à la tour intermédiaire, puis on déplace le plus grand disque restant de la tour de départ à la tour d’arrivée, et enfin on déplace le sous-ensemble de disques de la tour intermédiaire à la tour d’arrivée. Ce processus est répété de manière récursive jusqu’à ce que tous les disques soient déplacés à la tour d’arrivée.

En programmation, cette approche récursive peut être implémentée de manière élégante en utilisant une fonction récursive qui prend en compte le nombre de disques à déplacer ainsi que les tours de départ, intermédiaire et d’arrivée.

L’implémentation fournie dans le code Python précédent crée une classe TourDeHanoi qui représente le jeu et fournit des méthodes pour initialiser les tours, déplacer les disques et résoudre le puzzle en utilisant la récursivité. Cette approche permet de résoudre efficacement le puzzle des tours de Hanoï tout en illustrant les concepts de récursivité et de programmation orientée objet en Python.