El algoritmo de las Torres de Hanói

procedure hanoi(n, source, target, spare)
    if n == 0 then
        return
    hanoi(n - 1, source, spare, target)
    move disk n from source to target
    hanoi(n - 1, spare, target, source)
end procedure

En qué fijarse

• Los papeles rotan. La torre B es la libre para la primera llamada y el destino para la que esa llamada hace. Cada nivel de recursión reetiqueta las tres torres, y ese reetiquetado es todo el truco.
• La pila nunca se hace profunda. Tres discos nunca tienen más de 4 llamadas a la vez —una por cada número de discos, de 3 a 0— aunque el programa haga 15 llamadas en total.
• La mitad de las llamadas no hacen nada. De esas 15 llamadas, 8 son de cero discos y vuelven al instante. Son el precio del caso base más simple posible.
• La línea que mueve se ejecuta exactamente 2ⁿ − 1 veces. Siete, para tres discos, a lo largo de los 43 pasos de la ejecución.

El primero es el más difícil de pillar mientras el programa corre, porque cuando ocurre no se mueve nada en el tablero: solo cambian los nombres bajo las torres. Aquí está quieto: la primera llamada, las dos que hay debajo camino del movimiento 1, y la llamada que trae la pila de vuelta.

1. hanoi(3, A, C, B)

   La primera llamada: mover los 3 discos de A a C. Eso deja B como torre libre. Origen A, destino C, libre B.

2. hanoi(2, A, B, C)

   Su primera llamada. El disco 3 no puede moverse con los discos 1 y 2 encima, y esos no pueden ir a C, adonde se dirige el disco 3. Así que B, que hace un momento era la libre, es el destino, y C es la libre. Origen A, destino B, libre C.

3. hanoi(1, A, C, B)

   Un nivel más abajo, el mismo intercambio otra vez. Para despejar el disco 2, el disco 1 va a C, y B vuelve a ser la libre. Origen A, destino C, libre B.

4. hanoi(2, B, C, A)

   El disco 3 ya ha cruzado. La segunda llamada de la raíz trae los discos 1 y 2 de vuelta desde B encima de él, así que ahora B es el origen y A, donde empezaron todos los discos, es la libre. Origen B, destino C, libre A.

El segundo es más fácil de dudar que de comprobar, así que aquí está la ejecución entera con la altura de la pila en cada uno de sus pasos:

• La ejecución dura 43 pasos y hace 15 llamadas en total.
• El número de llamadas en la pila sube y baja entre 0 y 4, y llega a 4 en 8 de esos pasos: cada vez que una llamada sin discos que mover empieza y vuelve.
• La profundidad 4 es n + 1 para n = 3, y ningún paso de la ejecución la pasa.

El árbol de recursión

Dibuja cada llamada como una caja bajo la llamada que la hizo y el programa se convierte en un árbol. Coloca cada caja encima del número del movimiento que hace y aparece algo más: leer las cajas de izquierda a derecha da los movimientos en orden. Con tres discos, el movimiento propio de la primera llamada —el disco mayor— es el movimiento 4, justo en el medio, con la solución entera de tres movimientos para dos discos a cada lado.

1. Movimiento 1: la llamada con n = 1, de A a C, mueve el disco 1.
2. Movimiento 2: la llamada con n = 2, de A a B, mueve el disco 2, entre sus dos llamadas con n = 1.
3. Movimiento 3: la llamada con n = 1, de C a B, mueve el disco 1.
4. Movimiento 4: la llamada con n = 3, de A a C, mueve el disco 3, entre sus dos llamadas con n = 2.
5. Movimiento 5: la llamada con n = 1, de B a A, mueve el disco 1.
6. Movimiento 6: la llamada con n = 2, de B a C, mueve el disco 2, entre sus dos llamadas con n = 1.
7. Movimiento 7: la llamada con n = 1, de A a C, mueve el disco 1.

Esa simetría se mantiene en todos los tamaños. El movimiento 2ⁿ⁻¹ es siempre el disco mayor cruzando, y los movimientos anteriores y posteriores son la solución de (n − 1) discos jugada dos veces, con dos torres intercambiando sus papeles. Por eso una lista de movimientos de cualquier longitud se lee de un vistazo, y por eso la solución de cinco discos es la de cuatro, un movimiento, y otra vez la de cuatro.

Por qué es correcto

El algoritmo nunca rompe una regla y siempre termina, y la demostración es lo bastante corta como para darla entera. La afirmación, para todo n, es:

Si los n discos de arriba de la torre de origen son los discos 1 a n, y cualquier disco que esté en otra parte es mayor que n, entonces hanoi(n, source, target, spare) mueve esos n discos al destino, de forma legal, y no toca nada más.

Para n = 0 no hay nada que mover y no se toca nada.

Supongamos que la afirmación vale para n − 1. Entonces cada uno de los tres pasos es legal:

1. La primera llamada mueve los discos 1 a n − 1 a la torre libre. Tiene derecho: cualquier otro disco, incluido el disco n, es mayor que n − 1.
2. El disco n se mueve al destino. Ahora no tiene nada encima, y el destino solo contiene discos mayores que n.
3. La segunda llamada mueve los discos 1 a n − 1 de la torre libre al destino. Con derecho por la misma razón: el disco n, ahora debajo de ellos, es mayor.

Los n discos están en el destino y no se ha movido nada más. Por inducción, la afirmación vale para todo n, y el rompecabezas completo es el caso en que el origen tiene todos los discos.

1. Supuestola afirmación para n − 1

   La hipótesis dice que una llamada sobre n − 1 discos los mueve adonde se le diga, de forma legal, y no toca nada más. Aplicada aquí, lleva los discos 1 a n − 1 del origen a la torre libre. Tiene derecho: cualquier disco sobre el que pudiera posarlos —incluido el disco n— es mayor que cualquiera de los que lleva.

2. Demostrado aquíun movimiento legal

   Este es el único paso que la demostración tiene que argumentar por sí misma, y es un solo movimiento. El disco n está despejado, porque el paso anterior lo despejó. El destino no contiene más que discos mayores que n, porque todo lo menor está en la torre libre. Así que el movimiento es legal.

3. Supuestola afirmación para n − 1, otra vez

   La misma hipótesis, usada por segunda vez, trae los discos 1 a n − 1 de la torre libre al destino. Legal por la misma razón que antes: el disco n, ahora debajo de ellos, es mayor. Los n discos están en el destino y no se ha movido nada más, que es la afirmación para n.

La recurrencia, resuelta como toca

Sea T(n) el número de movimientos que hace el algoritmo para n discos. La función hace dos llamadas sobre n − 1 discos y un movimiento propio, y no hace ningún movimiento cuando no hay discos:

Para resolverla, sustituye la recurrencia en sí misma y busca el patrón. A esto se le llama desenrollar o telescopar:

Ver un patrón no es demostrarlo, así que confírmalo por inducción. T(0) = 0 = 2⁰ − 1. Y si T(n − 1) = 2ⁿ⁻¹ − 1, entonces T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 2 + 1 = 2ⁿ − 1. La forma cerrada es exacta para todo n.

Hay un tercer camino, y es una imagen que ya has visto. El árbol de recursión de arriba es un árbol binario completo: la raíz mueve n discos, las dos llamadas de debajo mueven n − 1 cada una, las cuatro de debajo mueven n − 2, y así. La profundidad k tiene por tanto 2ᵏ llamadas, el último nivel es la profundidad n − 1, y cada una de esas llamadas hace exactamente un movimiento. Suma los niveles y la cuenta sale como una serie geométrica:

Tres métodos —desenrollar, inducción y el árbol— y una sola respuesta. Que conviene conocer, porque hay un cuarto que se ofrece constantemente y es incorrecto.

La misma aritmética cuenta las llamadas. Cada llamada con n {">"} 0 discos hace dos más, así que hay C(n) = 2C(n − 1) + 1 llamadas con C(0) = 1, que se desenrolla a 2ⁿ⁺¹ − 1. Eso son 2ⁿ − 1 llamadas que mueven un disco, más 2ⁿ que vuelven enseguida.

Coste en tiempo y en memoria

Cada llamada hace una cantidad constante de trabajo además de sus dos llamadas recursivas, así que el tiempo de ejecución es proporcional al número de llamadas: Θ(2ⁿ). Ningún algoritmo más listo puede mejorarlo, porque la salida misma tiene 2ⁿ − 1 movimientos de largo, y 2ⁿ − 1 es un mínimo demostrado, no solo lo mejor que se ha encontrado. La demostración de que no hay solución más corta tiene su propia página: por qué el mínimo es 2ⁿ − 1.

La memoria es otra historia. Las llamadas no existen todas a la vez: una llamada termina antes de que empiece su hermana, así que la pila solo guarda una llamada por nivel, de n hasta 0. El espacio usado es Θ(n): sesenta y cinco marcos de pila para los sesenta y cuatro discos de la leyenda, que cualquier ordenador guarda sin enterarse. Lo que se acaba es el tiempo: 18.446.744.073.709.551.615 movimientos a mil millones por segundo siguen siendo 584 años.

Ese número es el de la leyenda, y la leyenda es más joven de lo que parece. Un templo donde unos sacerdotes mueven sesenta y cuatro discos de oro, y el fin del mundo cuando terminen, aparece impreso por primera vez en 1884, en un artículo que anunciaba un rompecabezas puesto a la venta en París el año anterior bajo el nombre de un profesor que no existía. Al ritmo de los monjes, un movimiento por segundo, al mundo le quedan 585 mil millones de años, unas cuarenta veces la edad actual del universo. El matemático que estaba detrás del rompecabezas y de la historia fue Édouard Lucas, que demostró a mano que 2¹²⁷ − 1 es primo y murió a los 49 años por la infección de un corte que le hizo un plato que se le cayó a un camarero en un banquete.

Pon números en esas fórmulas y los dos tipos de coste se separan. Cada disco de más duplica con creces los movimientos y las llamadas, y añade un único marco a lo más profundo que llega la pila:

La calculadora de movimientos mínimos saca los movimientos y el tiempo para cualquier número de discos, y la última fila —el tamaño de la leyenda— tiene una página propia.

Sin recursión

Los mismos movimientos se pueden producir con un bucle sencillo y dos reglas:

• Movimientos impares: el disco más pequeño avanza una torre por un circuito fijo: A → C → B si el número de discos es impar, A → B → C si es par.
• Movimientos pares: haz el único movimiento legal que no toca al disco más pequeño. Siempre hay exactamente uno.

Esas dos reglas reproducen la solución recursiva movimiento a movimiento; la página de la solución iterativa muestra por qué, y la juega en un tablero.

Hay una versión aún más extraña que no guarda ninguna torre: el disco, el origen y el destino del movimiento m se pueden leer de los dígitos binarios de m. Esa conexión, y el código Gray que se esconde dentro, están en Torres de Hanói, binario y código Gray.

Desde una posición que no es el principio

La función de manual da por hecho que todos los discos empiezan en la torre de origen. Dale un rompecabezas a medias y no tiene nada que decir. Un caso más lo arregla. Mira el disco mayor:

• ¿Ya está en la torre a la que tiene que llegar? No necesita ningún movimiento. Resuelve los discos menores mandándolos a esa misma torre.
• ¿Está en otra parte? Aparta los discos menores a la torre que no es ni donde está ni adonde va, muévelo y sigue como antes.

Esa versión encuentra la solución más corta desde cualquier posición legal, y es la que ejecuta el solucionador de las Torres de Hanói.

Compruébalo tú

Tres preguntas que la página ya ha contestado. Resuélvelas antes de abrirlas: si alguna no sale, la sección que se nombra junto a la respuesta es la que conviene releer.

1. Tres discos son siete movimientos. ¿Cuántos son 5 discos, y cuántos de esos mueven el propio disco 5?

   Ver la respuesta

   31 movimientos, que son 2⁵ − 1, y exactamente uno de ellos mueve el disco mayor. Todos los discos menos el mayor se mueven más de una vez, porque cada una de las dos mitades de la solución tiene que moverlos. La recurrencia, resuelta como toca.

2. hanoi(3, A, C, B) hace hanoi(2, A, B, C) como primera llamada. ¿Por qué el destino de esa llamada es B y no C?

   Ver la respuesta

   Porque el disco 3 va a C, y solo puede aterrizar ahí si C está vacía. Así que los dos discos que tiene encima han de aparcarse en otro sitio, y el único otro sitio es B. La torre a la que apunta una llamada es la que su primera llamada tiene que dejar despejada, y por eso dos de los tres argumentos intercambian su sitio al entrar. En qué fijarse.

3. Resolver 20 discos hace 2.097.151 llamadas. ¿Cuántas de ellas están en la pila en el mismo instante, como mucho?

   Ver la respuesta

   21: una por cada número de discos, de 20 a 0. Una llamada termina antes de que empiece su hermana, así que las llamadas nunca existen todas a la vez: el trabajo es exponencial y la memoria es lineal. Coste en tiempo y en memoria.

El algoritmo en tu lenguaje

La misma función en seis lenguajes, cada uno con un programa ejecutable, una explicación línea a línea, el tablero corriendo al lado y las cosas propias de ese lenguaje, que resultan importar en cuanto intentas contar los movimientos de sesenta y cuatro discos. Esas seis páginas están en inglés.

• Torres de Hanói en PythonENRecursive and iterative programs, why Python's recursion limit never bites here, and integers that simply do not overflow.
• Torres de Hanói en JavaScriptENWhy 2 ** 64 − 1 prints the wrong number, BigInt, and a generator that hands out one move at a time.
• Torres de Hanói en JavaENWhy (1L << 64) − 1 is zero, counting with BigInteger, and the same solution driven by an explicit stack.
• Torres de Hanói en CENUndefined shifts, uint64_t, and a loop that reads every move straight off the bits of the move number.
• Torres de Hanói en C++ENCollecting the moves in a std::vector, the 64-disk count checked by the compiler, and three pairs of towers in a loop.
• Torres de Hanói en C#ENTop-level statements, an iterator whose moves LINQ can query, and ulong, checked arithmetic and UInt128 for the move count.

Las palabras de esta página

Caso base

La versión del problema que una función recursiva contesta directamente, sin llamarse a sí misma. Es lo que detiene la recursión. Aquí es n = 0: no hay discos que mover, así que no hay nada que hacer y la llamada vuelve. Toda cadena de llamadas, por profunda que sea, termina en una de estas.

Caso recursivo

Todo lo que no es el caso base: la parte de la función que resuelve una versión menor del mismo problema y construye su respuesta a partir de ella. Aquí son las tres líneas que mueven n − 1 discos fuera del camino, mueven el disco n y devuelven los n − 1.

Pila de llamadas

La lista de llamadas a funciones que han empezado y aún no han terminado, la más reciente al final. Una llamada se añade cuando empieza y se quita cuando vuelve, así que la pila es la forma que tiene un programa de recordar adónde volver. Es lo que dibuja el panel de arriba, y es memoria de verdad: por eso su profundidad es el coste en espacio del algoritmo.

Marco de pila

Una entrada de la pila de llamadas: los argumentos y las variables locales de una sola llamada. Cada fila de la pila del panel es un marco, con su propia n y su propia idea de qué torre es el origen, cuál el destino y cuál la libre. Sesenta y cuatro discos necesitan sesenta y cinco marcos, que no es nada; el problema son los movimientos.

Telescopar

También llamado desenrollar: resolver una recurrencia sustituyéndola en sí misma hasta que el patrón sea evidente, y fijar entonces el número de sustituciones para que solo quede el valor inicial conocido. Se llama telescopar porque los términos del medio se pliegan como las secciones de un catalejo.

Θsaid “theta mayúscula”

Un ritmo de crecimiento que es a la vez cota superior e inferior: Θ(2ⁿ) significa que el coste crece como 2ⁿ, no solo que no crece más deprisa. O(2ⁿ) prometería únicamente el techo. Θ es aquí la notación honesta, porque este algoritmo hace de verdad 2ⁿ − 1 movimientos: no puede tener suerte y acabar antes.

Preguntas frecuentes

¿Cómo funciona el algoritmo recursivo de las Torres de Hanói?

Para mover n discos de una torre de origen a una de destino, primero mueve los n − 1 discos de arriba a la torre libre, después mueve el disco mayor al destino, y después mueve los n − 1 discos de la libre al destino. Cada uno de esos dos traslados menores es el mismo problema con un disco menos, así que la función se llama a sí misma para ellos, y una llamada sin discos que mover simplemente vuelve.

¿Las Torres de Hanói son divide y vencerás o programación dinámica?

Son divide y vencerás. El problema se divide en dos subproblemas de n − 1 discos, cada uno se vence por recursión, y el paso de combinación es un único movimiento del disco mayor. No es programación dinámica, y la memoización no ayuda, aunque los subproblemas sí se repitan de verdad. Con tres torres solo hay seis maneras de nombrar origen, destino y libre, así que hanoi(1, A, C, B) se llama dos veces al resolver tres discos. Guardarlo en caché no aporta nada, porque la respuesta a un subproblema es una lista de 2ᵏ − 1 movimientos, y reproducir una lista guardada de esa longitud cuesta lo mismo que producirla. Aquí el trabajo es la salida, y ninguna tabla acorta la salida.

¿Se aplica el Teorema Maestro a la recurrencia de las Torres de Hanói?

No. El Teorema Maestro cubre recurrencias de la forma T(n) = aT(n/b) + f(n), donde cada subproblema es una fracción del original. La recurrencia de las Torres de Hanói es T(n) = 2T(n − 1) + 1: el subproblema es un disco menor, no una fracción del tamaño. Desenrollarla da T(n) = 2ⁿ − 1 directamente, y la inducción lo confirma.

¿Hasta qué profundidad llega la recursión?

Con un caso base de n = 0, hay como mucho n + 1 llamadas en la pila a la vez: una por cada número de discos, de n a 0. Con un caso base de n = 1 son n. En cualquier caso la profundidad crece de forma lineal, y por eso la solución recursiva solo necesita O(n) de memoria aunque haga un número exponencial de movimientos.

¿Cuántas llamadas a función hace la solución recursiva?

2ⁿ⁺¹ − 1 llamadas cuando el caso base es n = 0: las 2ⁿ − 1 llamadas que mueven un disco, más 2ⁿ llamadas que no encuentran nada que mover y vuelven. Tres discos hacen 15 llamadas. Escrito con un caso base de n = 1, el mismo programa hace exactamente 2ⁿ − 1 llamadas, una por movimiento.

¿Es el algoritmo iterativo más rápido que el recursivo?

En nada que importe. Los dos tienen que producir 2ⁿ − 1 movimientos, así que los dos tardan un tiempo proporcional a 2ⁿ. La versión iterativa se ahorra el coste de las llamadas a función y no puede quedarse sin pila, pero aquí la recursión solo tiene n niveles de profundidad, así que quedarse sin pila no es un riesgo real para ningún número de discos que pudieras esperar.

¿Cómo es el algoritmo de las Torres de Hanói en un diagrama de flujo?

No se parece a gran cosa, y esa es la respuesta honesta. Un diagrama de flujo muestra el control pasando por unas cajas una vez, y la segunda caja de este algoritmo es el diagrama entero otra vez: tres niveles más abajo, con dos de las torres intercambiadas y un disco menos. Un diagrama de flujo no tiene notación para eso, así que un diagrama de la solución recursiva o está mal, o es una imagen de una sola llamada con dos cajas que dicen «llamar a hanoi», que no enseña nada que no enseñe el pseudocódigo de cuatro líneas. El diagrama que sí lo expresa es el árbol de recursión: cada llamada dibujada bajo la llamada que la hizo, con cada caja encima del movimiento que hace. Está en esta página, y leer sus cajas de izquierda a derecha da los movimientos en orden.

¿Puede el algoritmo resolver un rompecabezas que ya está a medias?

La versión de manual no: da por hecho que todos los discos empiezan en una torre. Se generaliza con un caso más —si el disco mayor ya está en su destino, sáltatelo y resuelve los discos de encima— y esa versión encuentra la solución más corta desde cualquier posición legal. El solucionador de este sitio ejecuta exactamente eso. Abrir el solucionador →