Tours de Hanoï

Trois tiges plantées sur une planche, une pile de disques rangés du plus grand au plus petit, et une règle unique : un disque ne se pose jamais sur un plus petit. Ta mission tient en une phrase : amener toute la tour sur la tige de droite, un disque à la fois. Cela paraît simple avec trois disques. Avec huit, tu comprends pourquoi ce casse-tête est célèbre depuis plus de cent quarante ans.

Le jeu est ici en dix niveaux, répartis en deux mondes. Le premier monde se joue à trois tiges et fait grandir la tour disque après disque : trois, quatre, cinq, six, sept, puis huit. Le second ouvre une quatrième tige, et tout change : la même tour se monte deux fois, trois fois plus vite. Tu finis à douze disques, sur quatre tiges, avec quatre-vingt-un coups pour seul horizon.

Le compteur affiche en permanence deux nombres : tes coups joués, et le minimum théorique. Ce minimum n'est pas une estimation, c'est le résultat d'un calcul exact, fait par le jeu pour chaque niveau. Tu sais donc toujours si tu joues bien, et de combien tu t'éloignes du chemin le plus court.

Comment jouer

1. Touche une tige. Son disque du dessus se soulève et reste en l'air, prêt à partir. C'est le seul disque que tu peux déplacer sur cette tige : les autres sont coincés dessous.
2. Touche une autre tige. Le disque glisse et retombe dessus. S'il est plus petit que le disque d'arrivée — ou si la tige est vide — le coup passe et le compteur avance d'un.
3. Si le coup est interdit, le disque tremble et revient à sa place : tu as essayé de poser un grand disque sur un plus petit. Rien n'est perdu, rien n'est compté, tu recommences.
4. Touche deux fois la même tige pour reposer le disque sans rien déplacer. Aucun coup n'est compté.

Il n'y a pas de glisser-déposer : on touche, puis on pose. Cela marche aussi bien au doigt sur un téléphone qu'à la souris, et cela évite les disques lâchés à côté.

Quatre boutons t'accompagnent :

• Annuler remonte le temps d'un coup, autant de fois que tu veux, jusqu'au départ. Le compteur redescend avec toi.
• Recommencer replace toute la tour sur la première tige et remet le compteur à zéro.
• Indice montre le prochain coup à jouer, avec une flèche qui va d'une tige à l'autre. Il a un prix, et le jeu te prévient avant : un niveau fini avec un indice ne rapporte que deux étoiles au maximum.
• Niveaux ouvre la carte des dix niveaux, avec les étoiles gagnées sur chacun.

Au clavier, les chiffres 1 à 4 désignent les tiges, les flèches gauche et droite déplacent le curseur d'une tige à l'autre, Entrée soulève ou pose, Retour arrière annule le dernier coup et Échap repose le disque en l'air. Le jeu se termine donc entièrement sans souris, avec un contour net sur la tige sélectionnée.

La règle qui fait tout le jeu

Une tour de disques ne se déplace pas en vrac. Pour poser le plus grand disque sur la tige d'arrivée, il faut que cette tige soit vide, et que tous les disques plus petits soient ailleurs, empilés hors du chemin. Autrement dit : avant de déplacer le grand, tu dois d'abord déplacer toute la tour qui se trouve au-dessus de lui.

C'est la clé du casse-tête, et le jeu te la dit au troisième niveau, en une phrase : pour n disques, on déplace les n−1 du dessus, puis le grand, puis encore les n−1. Une fois que tu tiens cette idée, tu ne peux plus te perdre : chaque tour se ramène à une tour plus petite, jusqu'à un seul disque, qu'on déplace sans réfléchir.

Cette façon de résoudre un problème en le ramenant à une version plus petite de lui-même porte un nom en informatique, la récursivité, et les Tours de Hanoï en sont l'exemple d'école. Tu n'as rien à apprendre par cœur : en jouant cinq niveaux, tu l'auras dans les doigts.

Le nombre minimal de coups

À trois tiges, le compte est implacable : un disque de plus double le travail, et ajoute un coup. Trois disques demandent 7 coups, quatre en demandent 15, cinq 31, six 63, sept 127, et huit 255. La formule tient en peu de signes : deux à la puissance n, moins un.

C'est cette croissance qui fait la légende attachée au jeu. On raconte que des moines déplacent, dans un temple, une tour de soixante-quatre disques d'or, et que le monde finira quand la tour sera achevée. À un coup par seconde, sans jamais se tromper, il leur faudrait plus de cinq cents milliards d'années. Le monde a encore le temps.

Le monde des quatre tiges

Avec une tige de plus, le casse-tête devient un autre jeu. Tu disposes de deux endroits où mettre les disques de côté au lieu d'un seul, et la bonne stratégie n'est plus de tout déplacer d'un bloc, mais de couper la tour en deux paquets.

Le principe : tu gares un paquet de petits disques sur une tige d'attente en profitant des quatre tiges ; tu déplaces le reste de la tour en n'utilisant plus que trois tiges, puisque la quatrième est occupée ; puis tu vas rechercher le paquet mis de côté. Tout l'art consiste à choisir la taille du paquet.

Le résultat est spectaculaire. Six disques demandent 63 coups à trois tiges, et seulement 17 à quatre. Huit disques passent de 255 à 33. Dix disques se font en 49 coups, et douze en 81. Le jeu calcule ces nombres lui-même, par la récurrence de Frame–Stewart, dont on sait depuis 2014 qu'elle donne bien le minimum absolu à quatre tiges.

Pour douze disques, le meilleur découpage met sept disques de côté : on les range sur une tige d'attente en 25 coups, on déplace les cinq gros à trois tiges en 31 coups, puis on ramène les sept petits en 25 coups. Vingt-cinq, plus trente et un, plus vingt-cinq : quatre-vingt-un.

Les étoiles et la progression

Chaque niveau se gagne avec une, deux ou trois étoiles :

• Trois étoiles si tu finis au nombre minimal de coups, sans indice.
• Deux étoiles si tu dépasses le minimum de 25 % au plus, arrondi au-dessus. Pour un niveau à 17 coups, cela laisse jusqu'à 22 coups ; pour un niveau à 81, jusqu'à 102.
• Une étoile dès que la tour est reconstruite, quel que soit le nombre de coups.

Une étoile suffit à déverrouiller le niveau suivant : personne ne reste bloqué. Mais la carte des niveaux garde la trace de ton meilleur résultat, étoiles et nombre de coups, et rien ne t'empêche de revenir sur un niveau déjà fini pour arracher la troisième étoile.

La progression est gardée dans ton navigateur. Il n'y a ni compte à créer, ni score envoyé quelque part, ni classement en ligne : ce jeu est un parcours personnel, à ton rythme. Si tu changes d'appareil ou si tu effaces les données de ton navigateur, tu repars des dix niveaux vierges.

Astuces

• Regarde le petit disque. À trois tiges, dans une partie jouée au plus court, il bouge un coup sur deux, et toujours dans le même sens de rotation. Si le nombre de disques est impair, il part vers la tige d'arrivée ; s'il est pair, vers la tige du milieu. Entre deux de ses déplacements, il n'y a jamais qu'un seul autre coup possible qui ne défait pas le précédent : tu peux jouer un niveau entier sans jamais hésiter.
• Ne défais pas ce que tu viens de faire. Ramener un disque là d'où il vient coûte deux coups pour rien. Si tu as cette envie, c'est souvent que le coup précédent était le mauvais : utilise Annuler plutôt que de tourner en rond.
• Pense à la tour du dessus, pas au disque du dessous. Avant de déplacer le grand disque, demande-toi où doit aller la pile qui le recouvre. Sa destination est toujours la tige que le grand disque n'utilise pas.
• À quatre tiges, compte tes paquets. Un bon découpage laisse à peu près autant de travail au paquet mis de côté qu'aux gros disques. Si tu gares trop peu de disques, la partie à trois tiges devient énorme ; si tu en gares trop, tu fais deux fois un long voyage.
• Vérifie ta tour toutes les deux ou trois minutes. Sur les grands niveaux, arrête-toi et regarde où sont les trois plus petits disques : s'ils sont éparpillés sur trois tiges différentes, tu as pris un détour.
• Un indice n'est pas une défaite. Deux étoiles avec la solution comprise valent mieux que dix minutes perdues. Tu pourras toujours recommencer le niveau proprement ensuite.

Questions fréquentes

À partir de quel âge peut-on jouer ? Dès cinq ou six ans pour les premiers niveaux : trois disques, une règle unique, et rien à lire. Les niveaux à huit disques et le monde des quatre tiges occupent très sérieusement un adulte.

Combien de coups faut-il au minimum ? À trois tiges, deux à la puissance n, moins un : 7 coups pour trois disques, 255 pour huit. À quatre tiges, le minimum est bien plus bas — 17 coups pour six disques, 81 pour douze — et le jeu l'affiche à côté de ton compteur, niveau par niveau.

Pourquoi la quatrième tige change-t-elle tout ? Parce qu'elle offre un second endroit où mettre les disques de côté. Au lieu de déplacer la tour entière d'un bloc, tu peux garer un paquet de petits disques, travailler tranquillement sur les gros, puis revenir chercher le paquet. Le nombre de coups ne double plus à chaque disque ajouté.

Annuler un coup fait-il baisser le compteur ? Oui. Le compteur indique la longueur du chemin que tu as effectivement parcouru depuis le départ : si tu annules, il redescend. Tu peux donc chercher, te tromper, revenir en arrière, et viser quand même les trois étoiles.

Que coûte un indice ? Il plafonne le niveau à deux étoiles, et le jeu te le dit avant de te le montrer : il faut toucher le bouton une seconde fois pour confirmer. En revanche, le nombre d'indices n'a pas d'importance : le premier a déjà tout coûté. Recommencer le niveau remet l'ardoise à zéro.

Le coup montré par l'indice est-il le meilleur ? À trois tiges, oui, toujours : le chemin le plus court se calcule exactement depuis n'importe quelle position. À quatre tiges, l'indice suit le chemin le plus court tant que tu es dessus, et te ramène au plus vite vers lui si tu t'en es écarté.

Peut-on jouer entièrement au clavier ? Oui. Les chiffres 1 à 4 désignent les tiges, les flèches déplacent le curseur, Entrée soulève et pose, Retour arrière annule. La tige sélectionnée est entourée d'un contour visible, et chaque coup est annoncé aux lecteurs d'écran.

D'où vient ce casse-tête ? Du mathématicien français Édouard Lucas, qui l'a mis en vente en 1883 sous un pseudonyme, avec la légende du temple et de ses soixante-quatre disques d'or. Depuis, il sert d'exemple dans tous les cours d'algorithmique du monde — et de jeu de patience dans toutes les salles d'attente.