Les tours de Hanoï
Déplacer toute la pile sur la dernière tige, un disque à la fois, sans jamais poser un grand sur un petit.
Les deux seules règles
Un seul disque se déplace à la fois, et c'est toujours celui du dessus d'une pile. Un disque ne peut jamais être posé sur un disque plus petit que lui. C'est tout, et cela suffit à produire un casse-tête que l'on peut passer un long moment à résoudre de travers.
L'objectif est d'amener la pile entière sur la tige C, dans le même ordre. La tige du milieu n'est pas un obstacle, c'est l'outil indispensable : rien ne se fait sans elle.
La méthode qui marche à tous les coups
Le raisonnement est récursif, et c'est ce qui rend ce jeu célèbre bien au-delà des salles de jeux. Pour déplacer une pile de quatre disques de A vers C, il faut d'abord déplacer les trois disques du dessus de A vers B, puis faire glisser le grand disque de A vers C, puis déplacer les trois disques de B vers C. Le problème à quatre disques se ramène donc à deux problèmes à trois disques, eux-mêmes ramenés à deux problèmes à deux disques, et ainsi de suite jusqu'au cas trivial d'un seul disque.
Il existe aussi une méthode purement mécanique, sans réflexion : déplacez alternativement le plus petit disque et le seul autre coup légal disponible. Le petit disque tourne toujours dans le même sens, de A vers C vers B vers A si le nombre de disques est pair, dans l'autre sens s'il est impair. Cette suite de coups résout la tour de façon optimale sans jamais avoir à réfléchir.
Pourquoi le nombre de coups double à chaque disque
Le minimum est de deux puissance n moins un. Trois disques demandent sept coups, quatre en demandent quinze, huit en demandent deux cent cinquante-cinq. Chaque disque ajouté double presque le travail, puisqu'il faut déplacer toute la pile au-dessus de lui, le bouger, puis la déplacer de nouveau.
| Disques | Coups minimum | À un coup par seconde |
|---|---|---|
| 3 | 7 | 7 secondes |
| 8 | 255 | 4 minutes |
| 20 | 1 048 575 | 12 jours |
| 64 | 18 446 744 073 709 551 615 | 585 milliards d'années |
La légende des soixante-quatre disques
Le jeu a été inventé en 1883 par le mathématicien français Édouard Lucas, qui le commercialisa sous le pseudonyme de N. Claus de Siam, anagramme de Lucas d'Amiens. Il l'accompagna d'une légende de son cru : dans un temple, des moines déplaceraient sans relâche soixante-quatre disques d'or, et le monde prendrait fin lorsqu'ils auraient terminé.
Le calcul rend la prophétie rassurante. À raison d'un déplacement par seconde et sans jamais commettre d'erreur, la tâche demanderait environ cinq cent quatre-vingt-cinq milliards d'années, soit une quarantaine de fois l'âge actuel de l'univers. La légende était une trouvaille commerciale, mais elle illustre parfaitement ce qu'est une croissance exponentielle.
Ce que ce casse-tête apprend en informatique
Les tours de Hanoï servent d'exemple canonique dans presque tous les cours de programmation, pour une raison précise : c'est l'un des rares problèmes dont la solution récursive tient en trois lignes alors que la solution itérative est nettement plus obscure. Il montre aussi la différence entre le nombre d'étapes d'un algorithme et sa complexité de description : trois lignes de code peuvent engendrer des milliards d'opérations.
Questions sur les tours
Peut-on résoudre le jeu avec quatre tiges ?
Oui, et cela va beaucoup plus vite. Le problème à quatre tiges porte le nom de casse-tête de Reve, et sa solution optimale n'a été démontrée qu'en 2014, plus d'un siècle après l'énoncé. La formule est nettement moins simple que celle à trois tiges.
Existe-t-il une position impossible à résoudre ?
Non. Toute position légale, quelle qu'elle soit, mène à la solution. C'est une différence notable avec le taquin, dont la moitié des mélanges sont mathématiquement inaccessibles.
Pourquoi le jeu s'arrête-t-il à huit disques ?
Parce que neuf disques demandent cinq cent onze coups au minimum, et que chaque coup passe ici par un envoi de formulaire. Au-delà de huit, la mécanique du jeu devient plus fastidieuse que le casse-tête lui-même.