🗼 Comment résoudre les Tours de Hanoï (méthode et astuce)

Par Miguel Arechaga

Les Tours de Hanoï sont un casse-tête mathématique avec plus d'un siècle d'histoire et une place d'honneur en informatique, car elles illustrent à merveille l'idée de « résoudre un problème en le découpant en problèmes plus petits ». On t'explique la méthode pour les résoudre à tous les coups.

Que sont les Tours de Hanoï ?

Il y a trois tours et une pile de disques de tailles différentes, empilés du plus grand (en bas) au plus petit (en haut) sur la première tour. Le but est de déplacer toute la pile sur la dernière tour, en respectant deux règles : on ne déplace qu'un disque à la fois et un grand disque ne peut jamais se retrouver sur un plus petit.

Comment on joue

1. Touche la tour de départ pour prendre le disque du dessus, puis la tour d'arrivée.
2. Tu ne peux jamais poser un disque plus grand sur un plus petit.
3. Tu gagnes quand tu as déplacé toute la pile sur la tour de droite.
4. Essaie de le faire en un minimum de coups. Tu peux choisir de 3 à 6 disques.

La méthode récursive (celle qui ne rate jamais)

Le secret, c'est de penser « de haut en bas ». Pour déplacer une pile de N disques de la tour A vers la C en utilisant la B comme appui, fais toujours la même chose :

1. Déplace les N−1 disques du dessus de A vers B (la tour auxiliaire).
2. Déplace le plus grand disque de A vers C.
3. Déplace les N−1 disques de B vers C, par-dessus le grand.

Chacun de ces « déplacer N−1 disques » se résout en répétant la même idée avec une pile plus petite. C'est un schéma qui se répète vers l'intérieur jusqu'à n'avoir plus qu'un seul disque, qu'on déplace directement.

L'astuce du nombre minimum

Le nombre minimum de coups pour N disques est exactement 2^N − 1 : 7 pour 3 disques, 15 pour 4, 31 pour 5 et 63 pour 6. Il existe même une astuce pratique : si tu déplaces toujours le plus petit disque dans le même sens circulaire et que, entre deux, tu joues le seul autre coup légal possible, tu résous le casse-tête en un minimum de coups sans réfléchir.

Les Tours de Hanoï sont un magnifique exercice de logique et de planification. Une fois que tu as compris le schéma récursif, résoudre n'importe quel nombre de disques n'est plus qu'une question de répéter la recette.

🏆 Classement des meilleures parties

Les Tours de Hanoï ont leur propre classement mondial : la partie que tu résous avec le moins de coups est enregistrée. Va dans Classement, onglet 🕹️ 1 Joueur, choisis « Tours de Hanoï » dans le menu déroulant et compare ton résultat à celui des autres joueurs, synchronisé avec ton compte. Pour que ton résultat compte, il te faut un compte gratuit sur MundoSudoku (juste un nom d'utilisateur et un mot de passe, sans adresse e-mail) : tu peux jouer sans compte, mais sans être connecté ton résultat n'est pas enregistré au classement.