Les tours de Hanoï

Déplacez toute la tour vers la dernière tige : un disque à la fois, jamais sur un disque plus petit.

Quel disque bouge à chaque coup ?

Les tours de Hanoï

Le jeu publié par Édouard Lucas en 1883. Une tour de disques est empilée sur la tige A, du plus grand au plus petit. Il faut la reconstruire sur la dernière tige en respectant deux règles :

  • on déplace un seul disque à la fois, celui du dessus d’une tige ;
  • on ne pose jamais un disque sur un disque plus petit.

Jouer

  • Glisser-déposer un disque d’une tige à l’autre (souris ou doigt), ou cliquer sur la tige de départ, puis sur la tige d’arrivée.
  • Clavier : 1 à 9 et 0 (tige 10) : la tige de départ, puis la tige d’arrivée ; ou ← → pour choisir une tige et Espace pour prendre ou poser le disque ; Échap : reposer le disque.
  • U ou Ctrl+Z : annuler · Y : rétablir · R : recommencer · I : indice · S : solution (lecture ou pause) · + − : vitesse · P : panneau · ? : cette aide.

Explorer

  • Combien de coups ? Chaque tour réussie sans indice ni solution inscrit votre meilleur résultat dans le tableau, et un ✓ apparaît quand vous atteignez le minimum. Remplissez la colonne des 3 tiges, cherchez la régularité… et devinez la formule !
  • Indice et solution : « Indice » montre le prochain coup optimal. « Solution » se débloque après 5 essais avec le même nombre de disques et de tiges (un essai compte quand la tour est réussie, ou quand on recommence après avoir joué au moins un coup) ; elle joue alors la solution optimale coup par coup, de 0,5 à 1000 coups par seconde, et le panneau « La récursivité » montre comment elle se construit. Une partie assistée ne compte pas dans le tableau.
  • Quel disque bouge ? Une barre par coup, de hauteur égale au numéro du disque. Cliquez ou glissez sur la bande pour revenir à n’importe quel coup. Avec la solution optimale, une régularité étonnante apparaît…
  • Plus de tiges : jusqu’à 10 tiges. On ne sait que depuis 2014 (Thierry Bousch) quelle stratégie est la meilleure avec 4 tiges ; pour 5 tiges ou plus, c’est un problème ouvert.

La légende

Lucas racontait que des prêtres déplacent une tour de 64 disques d’or et que le monde finira quand ils auront terminé. Combien de coups leur faut-il ? Trouvez la formule grâce à votre tableau, puis calculez combien de temps il leur faudrait à un coup par seconde.