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 :
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 :
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 :
Donc, quand \(n\) devient grand, on a :
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.
Discussion
There are no comments yet. Feel free to leave a reply using the form below.