Tours de Hanoï
Le problème original
FIG. 6.2 – Tours de Hanoï : le problème classique
Problème
Ce problème a été inventé par le mathématicien Edouard LUCAS, d’après une légende hindoue. Selon cette légende, des moines sont gardiens de trois tours. 64 disques d’or concentriques, de plus en plus petits, sont empilés dans une des tours. Les moines doivent les transférer dans une autre tour, avec une règle unique : aucun disque ne doit être posé sur un plus petit. Quand il auront terminé, ce sera la fin du monde.
Une autre légende assure que ce puzzle était utilisé dans un temple pour la discipline mentale des aspirants à l’éveil. . . C’est plutôt dans cette optique que nous l’utiliserons aussi !
Régles
- 3 poteaux ;
- un certain nombre de disques ;
- un déplacement à la fois ;
- aucun disque ne peut être posé sur un disque plus petit.
Résolution
Ce problème a toujours une solution. Il faut pour cela utiliser la troisième tour, comme lieu de stockage temporaire. Soit U le nombre de coups, n le nombre de disques, on calcule U par : U = 2n - 1.
Ce qui donne pour résultats :
| Disques | Nombre de coups |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| ... | ... |
| 64 | 18 446 744 073 709 551 615 |
