Vamos a escribir programas que resuelven la Torre de Hanói en Python y en C. Todos muestran la secuencia para llevar 3 discos del poste izquierdo al derecho. La idea está explicada en El algoritmo de la Torre de Hanói, así que aquí me centro en el código y en cómo ejecutarlo.

Resolverla con recursión en Python

Es la forma más básica. «Aparto los n−1 discos de arriba → muevo el disco n → devuelvo los n−1 discos» se convierte tal cual en una función.

def hanoi(n, src, dst, via, moves):
    if n == 0:
        return
    hanoi(n - 1, src, via, dst, moves)  # aparta los n-1 discos de arriba
    moves.append((n, src, dst))         # mueve el disco n
    hanoi(n - 1, via, dst, src, moves)  # devuelve los n-1 discos


moves = []
hanoi(3, "izquierda", "derecha", "centro", moves)
for i, (disc, src, dst) in enumerate(moves, 1):
    print(f"Movimiento {i}: disco {disc} de {src} a {dst}")
print(f"En total, {len(moves)} movimientos")

Guárdalo con el nombre hanoi.py y ejecútalo con python3 hanoi.py. La salida es esta:

Movimiento 1: disco 1 de izquierda a derecha
Movimiento 2: disco 2 de izquierda a centro
Movimiento 3: disco 1 de derecha a centro
Movimiento 4: disco 3 de izquierda a derecha
Movimiento 5: disco 1 de centro a izquierda
Movimiento 6: disco 2 de centro a derecha
Movimiento 7: disco 1 de izquierda a derecha
En total, 7 movimientos

Si cambias el 3 de hanoi(3, ...), resuelve cualquier número de discos. Eso sí, como los movimientos son 2ⁿ−1, con 20 discos son más de un millón y con 30, unos mil millones: enseguida es una cantidad enorme. Python tiene un límite de profundidad de recursión (por defecto, unos 1000 niveles), pero en la Torre de Hanói la profundidad es el número de discos más 1, así que el número de movimientos se vuelve excesivo antes de que sea un problema.

Resolverla sin recursión en Python

Es la forma que escribe, con bucles, los pasos de la solución a mano (las dos reglas del artículo sobre cómo resolverlo). Los postes se identifican con los números 0 (izquierda), 1 (centro) y 2 (derecha).

def hanoi_loop(n):
    names = ["izquierda", "centro", "derecha"]
    pegs = [list(range(n, 0, -1)), [], []]  # de abajo arriba
    order = [0, 2, 1] if n % 2 == 1 else [0, 1, 2]  # orden en que gira el 1
    pos = 0  # poste donde está el 1 (posición dentro de order)
    moves = []
    for m in range(1, 2 ** n):
        if m % 2 == 1:
            # movimiento impar: el 1 al poste siguiente en el sentido decidido
            a = order[pos]
            pos = (pos + 1) % 3
            b = order[pos]
        else:
            # movimiento par: entre los dos postes sin el 1, el pequeño sobre el grande
            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"Movimiento {i}: disco {disc} de {src} a {dst}")

La salida son exactamente los mismos 7 movimientos que la versión recursiva. Se ha comprobado que, con cualquier número de discos de 1 a 10, sale la misma secuencia que con la versión recursiva.

Obtenerla directamente con binario en Python

Es la forma que calcula qué se hace en el movimiento m sin recorrer los movimientos anteriores. El significado de las fórmulas está en el artículo sobre el algoritmo.

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


print(list(hanoi_bits(3)))

Al ejecutarlo sale [(1, 0, 2), (2, 0, 1), (1, 2, 1), (3, 0, 2), (1, 1, 0), (2, 1, 2), (1, 0, 2)]. Son tríos (disco, poste de origen, poste de destino) y coinciden con los 7 movimientos de arriba. Estas fórmulas dan la secuencia del poste 0 al poste 2 si el número de discos es impar, y del poste 0 al poste 1 si es par. Si con un número par de discos quieres llevarla a la derecha, úsala intercambiando los postes 1 y 2.

Resolverla con recursión en C

También en C la forma es la misma que 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("Movimiento %d: disco %d de %s a %s\n", count, n, src, dst);
    hanoi(n - 1, via, dst, src);
}

int main(void) {
    hanoi(3, "izquierda", "derecha", "centro");
    printf("En total, %d movimientos\n", count);
    return 0;
}

Guárdalo con el nombre hanoi.c, compílalo con cc -o hanoi hanoi.c y ejecútalo con ./hanoi. Se muestran los mismos 7 movimientos que con la versión recursiva de Python y «En total, 7 movimientos».

Tropiezos al escribirlo

  • Confundir el orden de los argumentos: en la primera llamada se intercambian el «poste auxiliar» y el «poste de destino», y en la segunda, el «poste de origen» y el «poste auxiliar». Si te equivocas aquí, salen movimientos que rompen las reglas.
  • Olvidar la condición de parada: si no paras en n == 0 (o en n == 1), se llama sin fin.
  • Cómo comprobarlo: aplica la secuencia obtenida a un tablero y comprueba que no haya ningún movimiento que ponga un disco grande sobre uno pequeño y que los movimientos sean 2ⁿ−1.