Algoritmo de la Torre de Hanoi: Python, C++ Code

¿Qué es la Torre de Hanoi?

La Torre de Hanoi es un rompecabezas matemático que consta de tres varillas y una pila de discos de tamaño decreciente colocados uno encima del otro. También se la conoce como la Torre de Brahma o la Torre de Lucas, ya que el matemático francés Édouard Lucas la introdujo en 1883. El rompecabezas se basa en leyendas sobre discos de oro que se movían entre tres varillas.

Este rompecabezas tiene tres varillas y un número variable de discos apilados. Las varillas están dispuestas en forma de torres cíclicas, de modo que los discos más grandes se apilan en la parte inferior y los más pequeños en la parte superior.

Inicialmente, se nos proporcionan tres clavijas o varillas. En una de ellas (la clavija A en el ejemplo) están apilados todos los discos. El objetivo es mover toda la pila de una varilla (A) a otra (C) siguiendo unas reglas específicas.

Aquí está la configuración inicial del rompecabezas:

Problema de la Torre de Hanoi

Y este es el objetivo final:

Reglas de la Torre de Hanoi

Estas son las reglas esenciales para la Torre de Hanoi:

• En la fase inicial del rompecabezas, todos los discos están apilados sobre la varilla uno.
• En la fase final, todos los discos de la varilla uno se apilan sobre la varilla dos o la varilla tres.
• En un momento dado, solo un disco puede moverse de una varilla a otra.
• Solo se puede mover el disco superior de la varilla.
• No se puede colocar un disco encima de otro más pequeño.

La leyenda original trataba sobre mover 64 discos. Los sacerdotes podían mover un disco a la vez según las reglas. Según la leyenda, existía una profecía que decía que el mundo se acabaría si lograban completar la hazaña. En la sección de complejidad temporal, demostraremos que una configuración de la Torre de Hanoi con n discos requiere 2^n – 1 movimientos.

Así pues, si los sacerdotes necesitaban 1 segundo para mover un disco, el tiempo total para resolver el rompecabezas sería de 2^64 – 1 segundos, o aproximadamente 584,942,417,356 años, 26 días, 7 horas y 15 segundos.

Algoritmo para la Torre de Hanoi

La forma más común de resolver la Torre de Hanoi es mediante un algoritmo recursivo. Primero, elegimos dos varillas como origen y destino; la varilla sobrante actúa como auxiliar o ayudante.

Estos son los pasos para resolver el rompecabezas de la Torre de Hanoi:

• Mueva los n-1 discos superiores desde la clavija de origen a la clavija auxiliar.
• Mueva el enésimo disco desde la clavija de origen a la clavija de destino.
• Mueva los n-1 discos restantes desde la clavija auxiliar a la clavija de destino.

Nota: Si disponemos de un solo disco, podemos moverlo directamente desde el origen hasta el destino.

Cómo resolver el rompecabezas de la Torre de Hanoi

Ilustremos el algoritmo para tres discos. Consideremos la clavija A como origen, la clavija B como auxiliar y la clavija C como destino.

Paso 1) Inicialmente, todos los discos están apilados en la clavija A.

En esta etapa: Origen = Clavija A, Destino = Clavija C, Ayudante = Clavija B.

Ahora, necesitamos mover los n-1 discos superiores desde la fuente al asistente.

Nota: Aunque solo podemos mover un disco a la vez, este paso reduce nuestro problema de 3 discos a un problema de 2 discos, que se resuelve mediante una llamada recursiva.

Paso 2) Al realizar una llamada recursiva desde la clavija A con la clavija B como destino, utilizamos la clavija C como auxiliar.

Observe que volvemos a la primera etapa del mismo problema de la Torre de Hanoi, pero ahora con dos discos. Movemos n-1 (es decir, un) disco desde la fuente hasta el ayudante, que mueve el disco más pequeño de la clavija A a la clavija C.

En esta etapa: Origen = clavija A, Destino = clavija B, Ayudante = clavija C.

Paso 3) Según el algoritmo, el enésimo (segundo) disco se transfiere ahora al destino, la clavija B.

En esta etapa: Origen = clavija A, Destino = clavija B, Ayudante = clavija C.

Paso 4) Ahora, movemos el disco n-1 (disco uno) desde la clavija auxiliar C hasta la clavija de destino B, siguiendo la tercera etapa del algoritmo.

En esta etapa: Origen = clavija A, Destino = clavija B, Ayudante = clavija C.

Paso 5) Tras completar la llamada recursiva, volvemos a la configuración anterior de la primera etapa del algoritmo.

Paso 6) En la segunda etapa, movemos el disco 3 desde la clavija de origen A hasta la clavija de destino C.

En esta etapa: Origen = clavija A, Destino = clavija C, Ayudante = clavija B.

Paso 7) La siguiente tarea consiste en trasladar los discos restantes desde el soporte (clavija B) hasta el destino (clavija C). En esta ocasión, utilizaremos la fuente original (clavija A) como soporte.

Paso 8) Dado que no podemos mover dos discos a la vez, hacemos una llamada recursiva para el disco 1. Según nuestro algoritmo, el destino en este paso es la clavija A.

En esta etapa: Origen = clavija B, Destino = clavija A, Ayudante = clavija C.

Paso 9) Nuestra llamada recursiva ha finalizado. Ahora movemos el disco 2 desde su origen hasta su destino.

En esta etapa: Origen = clavija B, Destino = clavija C, Ayudante = clavija A.

Paso 10) Finalizamos moviendo el disco restante n-1 (disco 1) del dispositivo auxiliar al dispositivo de destino.

En esta etapa: Origen = clavija A, Destino = clavija C, Ayudante = clavija B.

Apodo Code para la Torre de Hanoi

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
    IF disk == 1 THEN
        move disk from source to dest
    ELSE
        Tower_Of_Hanoi(disk - 1, source, helper, dest)
        move disk from source to dest
        Tower_Of_Hanoi(disk - 1, helper, dest, source)
    END IF
END Procedure

código de programa en C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
    if (num == 1) {
        cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
        return;
    }
    tower_of_hanoi(num - 1, source, helper, dest);
    cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
    tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
    int num;
    cin >> num;
    printf("The sequence of moves :\n");
    tower_of_hanoi(num, "I", "III", "II");
    return 0;
}

Salida:

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

código de programa en Python

def tower_of_hanoi(n, source, destination, helper):
    if n == 1:
        print("Move disk 1 from peg", source, "to peg", destination)
        return
    tower_of_hanoi(n - 1, source, helper, destination)
    print("Move disk", n, "from peg", source, "to peg", destination)
    tower_of_hanoi(n - 1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n, 'A', 'B', 'C')

Salida:

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

Complejidad de la Torre de Hanoi

Aquí se muestra la complejidad temporal y espacial de la Torre de Hanoi:

1) Complejidad temporal:

Volviendo al algoritmo, hacemos una llamada recursiva para (n-1) discos dos veces por llamada. Cada (n-1) recursión se divide en ((n-1)-1) recursiones, y así sucesivamente, hasta que llegamos al caso base de un solo disco.

Para tres discos:

• El disco 3 llama dos veces a la función recursiva del disco 2.
• El disco 2 llama dos veces a la función recursiva del disco 1.
• El disco 1 se mueve en tiempo constante, lo que da tiempo para resolver el problema de los tres discos.

Expresado como una recurrencia:

= 2 × (Tiempo para resolver para dos discos) + tiempo constante para mover el disco 3

= 2 × (2 × tiempo para resolver un disco + tiempo constante para mover el disco 2) + tiempo constante para mover el disco 3

= (2 × 2) × tiempo constante para mover el disco 1 + 2 × tiempo constante para mover el disco 2 + tiempo constante para mover el disco 3

Para n discos, esto se convierte en:

2^n-1 × tiempo constante para mover el disco 1 + 2^n-2 × tiempo constante para mover el disco 2 + ….

Esta progresión geométrica suma O(2ⁿ – 1), que se simplifica a O (2ⁿ), una complejidad temporal exponencial.

2) Complejidad espacial:

La complejidad espacial de la Torre de Hanoi es O(n). La recursión utiliza la pila de llamadas, cuya profundidad máxima es igual a n, el número de discos. Por eso, la complejidad espacial es O(n).

Preguntas Frecuentes