Vamos escrever programas que resolvem a Torre de Hanói em Python e C. Todos mostram a sequência para mover 3 discos da haste esquerda para a direita. A ideia está explicada em O algoritmo da Torre de Hanói, então aqui o foco é o código e como executar.

Resolvendo com recursão em Python

É a forma mais básica. “Tirar os n−1 de cima → mover o disco n → trazer os n−1 de volta” vira uma função, do jeito que está.

def hanoi(n, src, dst, via, moves):
    if n == 0:
        return
    hanoi(n - 1, src, via, dst, moves)  # tira os n-1 de cima
    moves.append((n, src, dst))         # move o disco n
    hanoi(n - 1, via, dst, src, moves)  # traz os n-1 de volta


moves = []
hanoi(3, "esquerda", "direita", "meio", moves)
for i, (disc, src, dst) in enumerate(moves, 1):
    print(f"Movimento {i}: disco {disc}, {src} -> {dst}")
print(f"Total: {len(moves)} movimentos")

Salve com o nome hanoi.py e execute com python3 hanoi.py, e a saída será esta.

Movimento 1: disco 1, esquerda -> direita
Movimento 2: disco 2, esquerda -> meio
Movimento 3: disco 1, direita -> meio
Movimento 4: disco 3, esquerda -> direita
Movimento 5: disco 1, meio -> esquerda
Movimento 6: disco 2, meio -> direita
Movimento 7: disco 1, esquerda -> direita
Total: 7 movimentos

Mudando o 3 de hanoi(3, ...), resolve-se qualquer quantidade de discos. Mas, como o número de movimentos é 2ⁿ−1, com 20 discos são cerca de 1 milhão e com 30, cerca de 1 bilhão, uma quantidade que logo fica enorme. O Python tem um limite de profundidade de recursão (uns 1000 níveis por padrão), mas a profundidade da recursão na Torre de Hanói é a quantidade de discos mais 1, então o número de movimentos fica grande demais antes de isso virar problema.

Resolvendo sem recursão em Python

É a forma que escreve, do jeito que está, com repetição, os passos de resolver à mão (as duas regras do artigo sobre como resolver). As hastes são tratadas pelos números 0 (esquerda), 1 (meio) e 2 (direita).

def hanoi_loop(n):
    names = ["esquerda", "meio", "direita"]
    pegs = [list(range(n, 0, -1)), [], []]  # de baixo para cima
    order = [0, 2, 1] if n % 2 == 1 else [0, 1, 2]  # ordem em que o 1 gira
    pos = 0  # haste onde está o 1 (que posição de order)
    moves = []
    for m in range(1, 2 ** n):
        if m % 2 == 1:
            # movimento ímpar: o 1 vai para a haste vizinha, no sentido definido
            a = order[pos]
            pos = (pos + 1) % 3
            b = order[pos]
        else:
            # movimento par: nas 2 hastes sem o 1, o menor vai para o maior
            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"Movimento {i}: disco {disc}, {src} -> {dst}")

A saída são os mesmos 7 movimentos da forma recursiva. Confirmamos que, com qualquer quantidade de 1 a 10 discos, sai a mesma sequência da forma recursiva.

Achando direto com binário em Python

É a forma que calcula o que fazer no movimento m sem percorrer os anteriores. O significado das fórmulas está no artigo sobre o algoritmo.

def hanoi_bits(n):
    for m in range(1, 2 ** n):
        disc = (m & -m).bit_length()     # zeros no final + 1
        src = (m & (m - 1)) % 3
        dst = ((m | (m - 1)) + 1) % 3
        yield disc, src, dst


print(list(hanoi_bits(3)))

Ao executar, sai [(1, 0, 2), (2, 0, 1), (1, 2, 1), (3, 0, 2), (1, 1, 0), (2, 1, 2), (1, 0, 2)]. São trios (disco, haste de origem, haste de destino), iguais aos 7 movimentos acima. Essa fórmula dá a sequência que move da haste 0 para a haste 2 com uma quantidade ímpar de discos e da haste 0 para a haste 1 com uma quantidade par, então, para mover uma quantidade par para a direita, use trocando as hastes 1 e 2.

Resolvendo com recursão em C

Em C, a forma é a mesma do 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("Movimento %d: disco %d, %s -> %s\n", count, n, src, dst);
    hanoi(n - 1, via, dst, src);
}

int main(void) {
    hanoi(3, "esquerda", "direita", "meio");
    printf("Total: %d movimentos\n", count);
    return 0;
}

Salve com o nome hanoi.c, compile com cc -o hanoi hanoi.c e execute com ./hanoi, e saem os mesmos 7 movimentos da forma recursiva em Python e “Total: 7 movimentos”.

Onde se costuma tropeçar ao escrever

  • Trocar a ordem dos argumentos: na 1ª chamada, trocam-se a “haste auxiliar” e a “haste de destino”, e na 2ª, a “haste de origem” e a “haste auxiliar”. Se errar aqui, aparecem movimentos que violam as regras.
  • Esquecer a condição de parada: sem parar em n == 0 (ou n == 1), as chamadas continuam para sempre.
  • Como conferir: aplique a sequência que saiu a um tabuleiro e confira se não há movimento que põe um disco grande sobre um menor e se o número de movimentos é 2ⁿ−1.