Tours de Hanoï

Le problème des tours de Hanoï est un divertissement mathématique conçu en 1883 par le mathématicien Édouard Lucas. De nos jours, c'est une excellente introduction à la récursion en mathématiques et à la récursivité en programmation.

Règles

Les règles sont les suivantes :

On dispose de trois piquets et de plusieurs disques de tailles différentes.
Initialement, tous les disques sont enfilés sur le premier piquet, du plus petit au plus grand, avec le plus petit au sommet.
Le but du jeu est de déplacer la pile de disques du premier au troisième piquet, sans jamais qu'un disque plus petit ne soit placé sous un disque plus gros que lui.
Un mouvement consiste à prendre un disque au sommet de l'un des trois piquets et à le déposer sur un autre piquet, si cela est possible.

Un joueur humain raisonnable peut espérer résoudre le problème pour un nombre de disques entre deux et cinq (31 coups) voire six (63 coups). En réalité, le nombre de coups croît de façon exponentielle, comme nous le verrons plus loin.

Résolution

Nous allons décomposer le problème récursivement. L'idée est que, pour transférer tous les \(n\) disques sur le troisième piquet, il suffit de transférer les \(n - 1\) premiers sur le piquet intermédiaire, puis de déplacer le plus gros disque du premier au dernier piquet avant de déplacer les \(n - 1\) disques du piquet intermédiaire sur le dernier piquet. Ainsi, résoudre le problème avec \(n\) disques revient à résoudre le problème pour \(n - 1\) disques, puis à effectuer quelques opérations bien prcises. Comme il est facile de trouver la solution pour 1 disque, on peut raisonner récursivement.

Pseudo-code

Supposons que l'on dispose d'une fonction deplacer(piquet A, piquet B) qui déplace le disque au sommet du piquet A sur le piquet B, ou retourne une erreur lorsque cela est impossible. On peut alors traduire le raisonnement précédent sous forme de pseudo-code :

Fonction hanoi(source, inter, dest, nombre_disques)
    Si nombre_disques = 1 :
        deplacer(source, dest)
    Sinon :
        hanoi(source, dest, inter, nombre_disques - 1)
        deplacer(source, dest)
        hanoi(inter, source, dest, nombre_disques - 1)

Ici, source désigne le piquet de départ du raisonnement, inter le piquet intermédiaire qu'on utilise pour stocker les \(n - 1\) disques, et dest est le piquet de destination sur lequel on souhaite déplacer tous les disques.

Implémentation en OCaml

On peut écrire la fonction deplacer de manière à afficher la liste des mouvements pour résoudre le problème. C'est ce qu'on fait dans l'exemple OCaml qui suit :

let deplacer source dest =
    print_string (source ^ " => " ^ dest);
    print_newline();;

let rec hanoi source inter dest n =
    let m1 = if n = 1 then 0 else hanoi source dest inter (pred n) in
    deplacer source dest;
    let m2 = if n = 1 then 0 else hanoi inter source dest (pred n) in
    (m1 + m2 + 1);;

On remarquera que la fonction hanoi retourne, au passage, le nombre de mouvements effectués. Essayons-là avec quatre piquets en utilisant des noms de camps fortifiés romains :

hanoi "Babaorum" "Laudanum" "Petibonum" 4;;

Cet appel de fonction imprime :

Babaorum => Laudanum
Babaorum => Petibonum
Laudanum => Petibonum
Babaorum => Laudanum
Petibonum => Babaorum
Petibonum => Laudanum
Babaorum => Laudanum
Babaorum => Petibonum
Laudanum => Petibonum
Laudanum => Babaorum
Petibonum => Babaorum
Laudanum => Petibonum
Babaorum => Laudanum
Babaorum => Petibonum
Laudanum => Petibonum

Cette solution comporte \(15 = 2^4 - 1\) coups. Nous allons maintenant voir pourquoi.

Nombre de coups nécessaires

Notons \(C_n\) le nombre de coups nécessaires pour résoudre le problème à \(n\) disques. On a directement :

\begin{equation*} C_1 = 1 \end{equation*}

Mais nous avons vu que, pour résoudre le problème avec \(n + 1\) disques, il fallait déplacer les \(n\) premiers disques sur le piquet intermédiaire, puis déplacer le plus gros disque sur le piquet final avec de déplacer les \(n\) autres disques du piquet intermédiaire au piquet final. Traduit mathématiquement, ce processus donne :

\begin{equation*} C_{n + 1} = 2 \times C_n + 1 \end{equation*}

Il s'agit d'une suite arithmético-géométrique que l'on sait résoudre de manière générique : sa solution est la somme de la solution homogène \(\lambda 2^n\) et d'une solution particulière, ici la constante -1. Le premier terme de la série \(C_1 = 1\) nous donne \(\lambda = 1\), de sorte que :

\begin{equation*} C_n = 2^n - 1 \end{equation*}

Donc, quand \(n\) devient grand, on a :

\begin{equation*} C_n \sim 2^n \end{equation*}

Et donc un nombre de coups exponentiel. Par exemple, \(C_{10} \approx 1.000\) et \(C_{20} \approx 1.000.000\).

Pour aller plus loin

Le petit tour d'horizon de ce classique touche à sa fin. Il y aurait encore beaucoup à dire sur ce problème, mais nous nous cantonnerons ici à des notions et méthodes générales. Pour de plus amples informations, vous pouvez consulter les articles qui suivent :

Tours de Hanoï sur Wikipédia, qui propose une autre solution itérative.
Implémentations de l'algorithme dans plus de 100 langages différents.