Le nombre total de mouvements requis pour déplacer 64 disques est de 264 - 1. Ce nombre est astronmoique (environ 18 trillions de trillions). Si un prêtre pouvait déplacer un disque par seconde, sans pause, il faudrait environ 595 milliards d'années pour accomplir la tâche, dépassant de loin l'âge actuel de l'univers.

Règles du Jeu

1. Un seul disque peut être déplacé à la fois.
2. Un disque plus grend ne peut jamais être placé sur un disque plus petit.
3. Les disques peuvent être déplacés entre trois aiguilles (source, destination, auxiliaire).

Approche Récursive

Pour résoudre le problème de manière systématique, on peut observer des motifs récursifs.

Cas de Base : 1 Disque

Déplacer un seul disque de l'aiguille source à l'aiguille de destination est trivial. Il suffit d'un seul mouvement.

Cas à 2 Disques

Pour déplacer deux disques de l'aiguille A vers l'aiguille C, en utilisant B comme auxiliaire :

1. Déplacer le plus petit disque (disque 1) de A vers B.
2. Déplacer le plus grand disque (disque 2) de A vers C.
3. Déplacer le plus petit disque (disque 1) de B vers C.

On peut voir cela comme la décomposition du problème principal en sous-problèmes plus petits :

1. Déplacer le disque 1 de A vers B.
2. Déplacer le disque 2 de A vers C.
3. Déplacer le disque 1 de B vers C.

Cas Général : N Disques

Pour déplacer N disques de l'aiguille Source (S) vers l'aiguille Destination (D), en utilisant l'aiguille Auxiliaire (A) :

1. Déplacer les N-1 disques supérieurs de l'aiguille S vers l'aiguille A, en utilisant D comme auxiliaire.
2. Déplacer le plus grand disque (le N-ième) de la'iguille S vers l'aiguille D.
3. Déplacer les N-1 disques de l'aiguille A vers l'aiguille D, en utilisant S comme auxiliaire.

Cette stratégie réduit le problème de N disques à des problèmes de N-1 disques, ce qui est la définition même de la récursion.

Implémentation du Code

La clé d'une implémentation récursive réside dans la définition claire du cas de base et de la fonction qui réduit le problème.

Fonction de Déplacement

Une fonction simple pour visualiser le déplacement des disques :

void DeplacerDisque(char origine, char destination) {
   printf("Déplacer de %c vers %c\n", origine, destination);
}
   

Fonction Récursive TourDeHanoi

Cette fonction prend le nombre de disques et les trois aiguilles comme paramètres.

// num: nombre de disques à déplacer
// origine: aiguille de départ
// destination: aiguille d'arrivée
// auxiliaire: aiguille temporaire
void TourDeHanoi(int num, char origine, char destination, char auxiliaire) {
   if (num == 1) {
       // Cas de base : un seul disque
       DeplacerDisque(origine, destination);
   } else {
       // Étape 1: Déplacer n-1 disques de l'origine vers l'auxiliaire
       TourDeHanoi(num - 1, origine, auxiliaire, destination);
       
       // Étape 2: Déplacer le plus grand disque de l'origine vers la destination
       DeplacerDisque(origine, destination);
       
       // Étape 3: Déplacer n-1 disques de l'auxiliaire vers la destination
       TourDeHanoi(num - 1, auxiliaire, destination, origine);
   }
}
   

Par exemple, pour déplacer 3 disques de l'aiguille A à C : TourDeHanoi(3, 'A', 'C', 'B');

Code Source Complet (C)

#include <stdio.h>

void DeplacerDisque(char origine, char destination) {
   printf("Déplacer de %c vers %c\n", origine, destination);
}

void TourDeHanoi(int num, char origine, char destination, char auxiliaire) {
   if (num == 1) {
       DeplacerDisque(origine, destination);
   } else {
       TourDeHanoi(num - 1, origine, auxiliaire, destination);
       DeplacerDisque(origine, destination);
       TourDeHanoi(num - 1, auxiliaire, destination, origine);
   }
}

int main() {
   printf("Solution pour 3 disques :\n");
   TourDeHanoi(3, 'A', 'C', 'B');
   return 0;
}
   

Code Source Complet (Java)

public class HanoiTower {

   public static void main(String[] args) {
       System.out.println("Solution pour 2 disques :");
       hanoi(2, 'A', 'C', 'B');
   }

   // Fonction récursive pour la Tour de Hanoï
   public static void hanoi(int numDisques, char source, char destination, char auxiliaire) {
       if (numDisques == 1) {
           deplacer(source, destination);
           return;
       }
       // Étape 1
       hanoi(numDisques - 1, source, auxiliaire, destination);
       // Étape 2
       deplacer(source, destination);
       // Étape 3
       hanoi(numDisques - 1, auxiliaire, destination, source);
   }

   // Fonction pour simuler le déplacement
   public static void deplacer(char source, char destination) {
       System.out.printf("Déplacer de %c vers %c\n", source, destination);
   }
}