Pour résoudre la tour de Hanoï, il n’y a que deux étapes à retenir. En les répétant à tour de rôle, on déplace la tour en un nombre minimal de coups, quel que soit le nombre de disques. Dans cet article, je décris le déplacement de la tour de la tige de gauche vers la tige de droite (pour les règles, voyez Qu’est-ce que la tour de Hanoï ?). J’appelle les disques 1, 2, 3… du plus petit au plus grand.

Deux étapes à répéter

  1. Aux coups impairs (1er, 3e, 5e coup…) : déplacer le plus petit disque (1) sur la tige voisine, dans un sens fixe.
  2. Aux coups pairs (2e, 4e, 6e coup…) : jouer le coup possible qui ne concerne pas le 1. Il n’y en a toujours qu’un.

C’est tout. Le 1 bouge un coup sur deux, et entre-temps, un autre disque bouge une fois.

Comment choisir le sens du petit disque

Le sens dans lequel on déplace le 1 dépend du nombre de disques. Imaginez les trois tiges comme un anneau : arrivé au bout, on repart à l’autre bout. Pour déplacer la tour de gauche à droite, l’ordre est le suivant.

Nombre de disquesOrdre des déplacements du 1
Impair (3, 5, 7…)gauche → droite → milieu → gauche…
Pair (4, 6, 8…)gauche → milieu → droite → gauche…

Pour s’en souvenir : « avec un nombre impair de disques, on pose le 1 directement, au premier coup, sur la tige d’arrivée ». Avec un nombre pair, au premier coup, on le pose sur l’autre tige (le milieu). Une fois le sens choisi, on ne le change plus jusqu’à la fin.

Pour viser la tige centrale, on échange « droite » et « milieu » dans le tableau.

Vérifier avec 3 disques

Il y a 3 disques (un nombre impair), donc le 1 tourne dans l’ordre « gauche → droite → milieu → gauche ». Le disque doré est celui qui vient de bouger.

  1. 321 Départ
  2. 321 Coup 1 1 à droite
  3. 321 Coup 2 2 au milieu
  4. 321 Coup 3 1 au milieu
  5. 213 Coup 4 3 à droite
  6. 123 Coup 5 1 à gauche
  7. 132 Coup 6 2 à droite
  8. 321 Coup 7 1 à droite

On voit qu’aux coups 1, 3, 5 et 7, c’est le 1 qui tourne, et qu’aux coups 2, 4 et 6, c’est « l’unique coup possible sans le 1 ».

Pourquoi le coup pair est unique

Aux coups pairs, on compare les disques du haut des deux tiges qui ne portent pas le 1. On ne peut que déplacer le plus petit sur le plus grand (ou sur une tige vide).

  • On ne peut rien poser sur le 1 (aucun disque n’est plus petit que 1).
  • Parmi les deux autres tiges, on ne peut pas poser un grand disque sur un petit.

Le coup possible est donc toujours unique. Seul le sens du 1 aux coups impairs peut faire hésiter, et si on le décide au départ, les coups suivent ensuite sans réfléchir.

L’idée « écarter le haut, porter le grand »

À part retenir les étapes, il y a une autre façon de comprendre pourquoi cela marche. Pour déplacer une tour de n disques de la gauche vers la droite, on la divise en trois :

  1. Écarter les n − 1 disques du haut sur la tige centrale.
  2. Porter le plus grand disque sur la tige de droite.
  3. Déplacer les n − 1 disques du milieu sur la tige de droite.

Les étapes 1 et 3 sont le problème « déplacer une tour avec un disque de moins », donc on peut réutiliser la même idée. Pour 4 disques : « écarter 3 disques → porter le 4 → remettre 3 disques » ; pour écarter 3 disques : « écarter 2 disques → porter le 3 → remettre 2 disques »… On se ramène ainsi à des problèmes de plus en plus petits. Cette idée montre aussi que le nombre de coups est 2ⁿ − 1 (la formule du nombre minimal de coups).

Se rattraper quand on se perd

Même si vous avez oublié la méthode et que les disques sont dans un désordre complet, pas de panique. Avec l’idée suivante, on peut se rattraper de n’importe quelle disposition.

  1. Parmi les disques qui ne sont pas encore bien empilés sur la tige de droite, cherchez le plus grand. C’est le prochain disque à porter.
  2. Pour le porter à droite, il faut avoir rassemblé tous les disques plus petits sur la troisième tige, qui n’est ni celle où il se trouve ni celle de droite.
  3. Rassembler les petits disques se fait avec la même idée, répétée. On prend la tige où on les rassemble pour « tige d’arrivée », et on recommence depuis le 1.

L’astuce est de décider la destination en commençant par les grands disques. Le mode « Puzzles » de l’app (remettre en forme de modèle des disques en désordre) se résout aussi avec cette idée.

Astuces

  • Compter les coups : aux coups impairs, on bouge toujours le 1, donc si vous savez à quel coup vous êtes, vous ne doutez pas du disque à déplacer.
  • Plus un disque est grand, moins il bouge : le 1 bouge un coup sur deux, mais le plus grand disque ne bouge qu’une fois. Si vous déplacez souvent un grand disque, vous faites un détour.
  • Commencer avec 3 ou 4 disques : tant que les deux étapes ne sont pas dans les mains, répétez plusieurs fois avec peu de disques. Quand vous êtes à l’aise, passez à 5, puis 7 disques.

Les solutions pour chaque nombre de disques

Les coups pour chaque nombre de disques et les formes repères sont rassemblés dans ces articles.

Essayer en jouant

Essayez les deux étapes sur le plateau ci-dessous. Touchez une tige pour soulever le disque du haut, puis touchez une autre tige pour le poser. Il commence avec 4 disques (un nombre pair), donc au premier coup, on déplace le 1 au milieu.

4321
Coups : 0 (minimum 15)

Déplacez toute la tour de la tige gauche vers la tige droite. Touchez une tige pour soulever son disque du haut.