Voici des programmes qui résolvent la tour de Hanoï, en Python et en C. Tous affichent les coups pour déplacer 3 disques de la tige de gauche vers la tige de droite. L’idée est expliquée dans l’algorithme de la tour de Hanoï ; ici, je me concentre sur le code et sur son exécution.

Résoudre en Python avec la récursivité

C’est la forme la plus simple. On écrit directement dans une fonction : « écarter les n − 1 disques du haut → déplacer le disque n → remettre les n − 1 disques ».

def hanoi(n, src, dst, via, moves):
    if n == 0:
        return
    hanoi(n - 1, src, via, dst, moves)  # écarter les n-1 disques du haut
    moves.append((n, src, dst))         # déplacer le disque n
    hanoi(n - 1, via, dst, src, moves)  # remettre les n-1 disques


moves = []
hanoi(3, "gauche", "droite", "milieu", moves)
for i, (disc, src, dst) in enumerate(moves, 1):
    print(f"Coup {i} : disque {disc}, {src} → {dst}")
print(f"{len(moves)} coups au total")

Enregistrez-le sous le nom hanoi.py et lancez python3 hanoi.py : voici ce qui s’affiche.

Coup 1 : disque 1, gauche → droite
Coup 2 : disque 2, gauche → milieu
Coup 3 : disque 1, droite → milieu
Coup 4 : disque 3, gauche → droite
Coup 5 : disque 1, milieu → gauche
Coup 6 : disque 2, milieu → droite
Coup 7 : disque 1, gauche → droite
7 coups au total

En changeant le 3 de hanoi(3, ...), on résout avec n’importe quel nombre de disques. Mais comme le nombre de coups est 2ⁿ − 1, il devient vite énorme : environ un million de coups pour 20 disques, environ un milliard pour 30. Python limite la profondeur de récursivité (environ 1 000 niveaux par défaut), mais la profondeur de récursivité de la tour de Hanoï est le nombre de disques plus 1, donc le nombre de coups devient trop grand bien avant que ce soit un problème.

Résoudre en Python sans récursivité

C’est la méthode à la main (les deux règles de l’article sur la façon de résoudre le jeu) écrite telle quelle avec une boucle. Les tiges sont désignées par les numéros 0 (gauche), 1 (milieu) et 2 (droite).

def hanoi_loop(n):
    names = ["gauche", "milieu", "droite"]
    pegs = [list(range(n, 0, -1)), [], []]  # du bas vers le haut
    order = [0, 2, 1] if n % 2 == 1 else [0, 1, 2]  # l’ordre où tourne le disque 1
    pos = 0  # la tige du disque 1 (quelle place dans order)
    moves = []
    for m in range(1, 2 ** n):
        if m % 2 == 1:
            # coup impair : le disque 1 sur la tige voisine, dans le sens choisi
            a = order[pos]
            pos = (pos + 1) % 3
            b = order[pos]
        else:
            # coup pair : parmi les deux tiges sans le disque 1, le plus petit sur le plus grand
            a, b = [p for p in range(3) if p != order[pos]]
            if not pegs[a] or (pegs[b] and pegs[b][-1] < pegs[a][-1]):
                a, b = b, a
        pegs[b].append(pegs[a].pop())
        moves.append((pegs[b][-1], names[a], names[b]))
    return moves


for i, (disc, src, dst) in enumerate(hanoi_loop(3), 1):
    print(f"Coup {i} : disque {disc}, {src} → {dst}")

L’affichage est exactement les mêmes 7 coups que la version récursive. J’ai vérifié que, pour tous les nombres de disques de 1 à 10, on obtient la même suite de coups que la version récursive.

Python : trouver directement à partir du binaire

Cette version calcule ce qu’il faut faire au coup m, sans refaire les coups précédents. Le sens des formules est expliqué dans l’article sur l’algorithme.

def hanoi_bits(n):
    for m in range(1, 2 ** n):
        disc = (m & -m).bit_length()     # nombre de 0 à la fin + 1
        src = (m & (m - 1)) % 3
        dst = ((m | (m - 1)) + 1) % 3
        yield disc, src, dst


print(list(hanoi_bits(3)))

À l’exécution, on obtient [(1, 0, 2), (2, 0, 1), (1, 2, 1), (3, 0, 2), (1, 1, 0), (2, 1, 2), (1, 0, 2)]. Ce sont des triplets (disque, tige de départ, tige d’arrivée), identiques aux 7 coups ci-dessus. Ces formules donnent les coups pour aller de la tige 0 à la tige 2 si le nombre de disques est impair, et de la tige 0 à la tige 1 s’il est pair. Pour viser la tige de droite avec un nombre pair de disques, on échange les tiges 1 et 2.

Résoudre en C avec la récursivité

En C aussi, la forme est la même qu’en Python.

#include <stdio.h>

static int count = 0;

void hanoi(int n, const char *src, const char *dst, const char *via) {
    if (n == 0) return;
    hanoi(n - 1, src, via, dst);
    count++;
    printf("Coup %d : disque %d, %s -> %s\n", count, n, src, dst);
    hanoi(n - 1, via, dst, src);
}

int main(void) {
    hanoi(3, "gauche", "droite", "milieu");
    printf("%d coups au total\n", count);
    return 0;
}

Enregistrez-le sous le nom hanoi.c, compilez-le avec cc -o hanoi hanoi.c et lancez ./hanoi : on obtient les mêmes 7 coups que la version récursive en Python, et la dernière ligne indique « 7 coups au total ».

Là où l’on se trompe en écrivant

  • Se tromper dans l’ordre des arguments : au premier appel, on échange la tige auxiliaire et la tige d’arrivée ; au second, la tige de départ et la tige auxiliaire. Si l’on se trompe ici, on obtient des coups qui violent les règles.
  • Oublier la condition d’arrêt : si l’on ne s’arrête pas à n == 0 (ou n == 1), on appelle sans fin.
  • Comment vérifier : appliquez les coups obtenus à un plateau, et vérifiez qu’aucun coup ne pose un grand disque sur un petit et que le nombre de coups est 2ⁿ − 1.