Tours de Hanoï

Comment jouer aux tours de Hanoï

Le casse-tête comporte trois tiges et une pile de disques de tailles différentes, empilés sur la première tige du plus grand en bas au plus petit en haut. Ton but : déplacer toute la pile sur la troisième tige. Il n'y a que deux règles :

1. Tu ne peux déplacer qu'un disque à la fois, pris en haut d'une pile.
2. Un disque ne peut jamais être posé sur un plus petit.

Touche une tige pour soulever son disque du dessus, puis touche la tige où tu veux le poser. Touche à nouveau la même tige pour le remettre en place. Le compteur affiche le nombre de coups joués et le minimum possible pour ta tour. Si tu finis en exactement ce nombre de coups, tu as trouvé la solution parfaite.

La solution la plus courte : 2ⁿ − 1 coups

Le casse-tête a une magnifique solution récursive. Pour déplacer une tour de n disques de la tige 1 à la tige 3 :

1. Écarte les n − 1 disques du dessus en les posant sur la tige 2.
2. Déplace le plus grand disque sur la tige 3.
3. Ramène les n − 1 disques de la tige 2 sur la tige 3, par-dessus le grand.

Les étapes 1 et 3 sont le même casse-tête avec un disque de moins : le nombre de coups double donc, plus un, à chaque disque ajouté : 1, 3, 7, 15, 31, 63, 127, 255. En général, une tour de n disques demande 2ⁿ − 1 coups, et aucune solution ne peut être plus courte. Touche Voir la solution pour la regarder se dérouler.

Une règle à suivre sans réfléchir

Il existe aussi une méthode pas à pas toute simple. Alterne entre deux types de coups :

• Coups impairs : déplace le plus petit disque d'une tige, toujours dans le même sens. Avec un nombre pair de disques, il voyage 1 → 2 → 3 → 1 ; avec un nombre impair, 1 → 3 → 2 → 1.
• Coups pairs : joue le seul coup permis qui ne touche pas au plus petit disque. Il y en a toujours exactement un.

En suivant ces deux règles, tu finis à chaque fois avec le nombre minimum de coups. Il y a même un lien avec le comptage en binaire : au coup numéro m, le disque qui bouge dépend du nombre de fois que 2 divise m. Le plus petit disque bouge à chaque coup impair, le deuxième aux coups 2, 6, 10, et ainsi de suite.

L'histoire et la légende

Les tours de Hanoï ont été inventées par le mathématicien français Édouard Lucas et vendues comme jouet en 1883 sous le nom malicieux de « N. Claus de Siam », anagramme de « Lucas d'Amiens ». Le jeu était accompagné d'une légende : dans un grand temple, des prêtres déplacent une tour de 64 disques d'or selon ces mêmes règles, et quand ils auront fini, le monde s'arrêtera.

La légende nous laisse un peu de répit. Une tour de 64 disques demande 2⁶⁴ − 1 coups, un peu plus de 18 milliards de milliards. À un coup par seconde, sans la moindre erreur, il faudrait environ 585 milliards d'années, bien plus que l'âge actuel de l'univers. Le casse-tête est depuis devenu un exemple favori pour enseigner la récursivité en mathématiques et en programmation, et la psychologie l'utilise pour étudier la planification.

Questions fréquentes

Quel est le nombre minimum de coups ?

Pour une tour de n disques, le minimum est de 2ⁿ − 1 coups : 7 avec 3 disques, 15 avec 4, 31 avec 5, 63 avec 6, 127 avec 7 et 255 avec 8.

Faut-il déplacer la tour sur la troisième tige ?

Oui, ici le but est la tige 3, celle de droite. La tige du milieu sert d'intermédiaire. La solution la plus courte a la même longueur dans les deux sens.

L'annulation compte-t-elle comme un coup ?

Non. Annuler revient sur ton dernier coup et retire un au compteur : tu peux donc explorer sans pénalité.

Que signifie le record ?

Ton record est la plus grande tour que tu as résolue. Commence avec 3 ou 4 disques et monte petit à petit. Résoudre 8 disques, en 255 coups ou plus, est un vrai test de patience et de planification.

Est-ce gratuit ?

Oui, entièrement gratuit et sans inscription. Ta progression est enregistrée dans ton navigateur, sur ton propre appareil.