Torres de Hanói: preguntas frecuentes

Lo hay, y es mecánico más que ingenioso: en cada movimiento impar, mueve el disco más pequeño una torre en la misma dirección —a la izquierda si el número de discos es impar, a la derecha si es par, dando la vuelta en los extremos, de modo que con tres discos su primer movimiento da la vuelta de A a C—. En cada movimiento par solo hay un movimiento legal que no toca al disco más pequeño, así que lo haces sin pensar. Alternando los dos juegas una partida perfecta sin planear ni un paso. La página de estrategias lo desarrolla.

Empieza con la pila entera en la torre izquierda, el disco menor arriba. El objetivo es la misma pila en la torre derecha. Tres reglas: un disco a la vez, siempre el disco superior de una torre, y nunca un disco mayor sobre uno menor. Con tres discos la partida más corta son siete movimientos en tres grupos: A→C, A→B, C→B construye los dos discos menores en la torre central; A→C deja cruzar al disco mayor; y B→A, B→C, A→C reconstruye esos dos encima de él. Cómo jugar, con un tablero de práctica.

Fáciles de aprender, y difíciles en un solo sentido: se alargan al doble con cada disco que añades. Tres discos son siete movimientos, y casi todo el mundo —niños desde unos seis años— termina al primer intento. Alrededor de cinco o seis discos el ensayo y error deja de funcionar y hace falta un método, y lo difícil del método es fiarse de movimientos que parecen ir hacia atrás, como amontonar una pila entera en la torre central cuando el objetivo está a la derecha. Una vez que la idea recursiva encaja, todos los tamaños son el mismo rompecabezas. Por qué la idea recursiva es todo el rompecabezas.

No hay ningún organismo que homologue récords de velocidad de las Torres de Hanói como sí lo hay para el cubo de Rubik, así que los tiempos que se anuncian no son comparables y normalmente no dicen con cuántos discos se jugó, que es el único dato que importa. Mejor calcúlalo: una partida perfecta de n discos son 2ⁿ − 1 movimientos, y quien tiene práctica mantiene unos dos movimientos por segundo. Eso son unos cuatro segundos para tres discos, unos nueve minutos para diez discos y sus 1023 movimientos, y unas cuatro horas y media para 15 discos y sus 32.767. El tablero de este sitio guarda tu menor número de movimientos para cada cantidad de discos en tu navegador, y muestra tu tiempo en la pantalla de resultado. La calculadora da el tiempo para cualquier tamaño.

2ⁿ − 1, y es un suelo demostrado, no el mejor resultado conocido. Tres discos necesitan 7 movimientos, cuatro necesitan 15, cinco necesitan 31, diez necesitan 1023 y 15 necesitan 32.767. La demostración tiene dos mitades: el método recursivo alcanza ese número, y ninguna solución puede mejorarlo, porque el disco mayor tiene que moverse al menos una vez y todos los discos menores que están encima han de apartarse antes a la torre libre y volver después. Las dos mitades de la demostración, completas.

T(n) = 2·T(n − 1) + 1, con T(0) = 0. Se lee directamente del método: para mover n discos apartas n − 1 discos, mueves un disco al otro lado y vuelves a mover esos n − 1 discos; dos soluciones más pequeñas más un único movimiento. Desplegándola se obtiene T(n) = 2ⁿ − 1, que puedes comprobar por inducción: si T(n − 1) = 2ⁿ⁻¹ − 1, entonces T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1. Resolver la recurrencia, paso a paso.

No en el sentido computacional, a pesar del número exponencial de movimientos. El algoritmo ocupa unas pocas líneas, decidir el siguiente movimiento lleva tiempo constante, y la solución solo es exponencialmente larga porque la respuesta lo es: imprimir 2ⁿ − 1 movimientos no puede hacerse en menos de 2ⁿ − 1 pasos. No es NP-difícil, y encontrar la ruta más corta entre dos posiciones legales cualesquiera con tres varillas también se resuelve de forma eficiente. La versión genuinamente difícil es la de cuatro varillas, cuya solución óptima se conjeturó en 1941 y no se demostró hasta que Thierry Bousch la resolvió en 2014. El algoritmo y lo que cuesta.

Con el método de Frame–Stewart. Con cuatro varillas ya no mueves n − 1 discos de golpe: eliges un corte k, mueves los k discos de arriba a una varilla libre usando las cuatro varillas, mueves los n − k discos restantes al destino usando solo tres —la libre está ocupada, así que esa parte es el rompecabezas clásico— y después colocas encima los k discos. Probando todos los k y quedándote con el mejor se obtiene la cuenta óptima, que se desploma espectacularmente: 15 discos bajan de 32.767 movimientos con tres varillas a 129 con cuatro. Juega al rompecabezas de cuatro varillas.

Divide y vencerás, expresado como recursión. La solución estándar es una sola función —mover n − 1 discos del origen a la varilla libre, mover el disco n del origen al destino, mover esos n − 1 discos de la libre al destino— con un caso base que no hace nada cuando n llega a cero. Hay un algoritmo iterativo equivalente que no usa recursión en absoluto: mover repetidamente el disco más pequeño una torre en una dirección fija y después hacer el único otro movimiento legal. Ambos producen exactamente la misma secuencia de movimientos, porque la solución óptima es única. El algoritmo, línea a línea.

Una función recursiva y tres parámetros: void hanoi(int n, char from, char to, char via) — si n es cero, return; si no, llama a hanoi(n − 1, from, via, to), imprime el movimiento from → to y llama a hanoi(n − 1, via, to, from). Invócala como hanoi(3, 'A', 'C', 'B'). Recoge los movimientos en un std::vector<std::pair<char, char>> en lugar de imprimirlos si quien llama los necesita, y deja n como un int normal: con un parámetro sin signo, una cuenta negativa pasada por error se convierte en unos cuatro mil millones sin avisar, y la recursión corre hasta desbordar la pila en vez de fallar una simple comprobación n &lt; 0. El programa completo en C++, explicado línea a línea.

Son dos usos distintos de una pila, y conviene no mezclarlos. Las varillas son pilas: cada torre es último en entrar, primero en salir, solo tocas el disco de arriba, y un movimiento es sacar de una torre y meter en otra, que es por lo que la comprobación de la regla es una única comparación contra la cima del destino. Aparte, una pila explícita puede sustituir a la recursión: mete el trabajo entero (n, from, to, via) y después repite: saca un trabajo y, si le quedan discos, mete sus tres partes en orden inverso: el segundo traslado, el movimiento único del disco n y el primer traslado. El orden inverso importa porque una pila devuelve primero lo último que se metió. Eso es lo que el entorno de ejecución del lenguaje hace por ti en la versión recursiva. La solución sin recursión alguna.

En IA el rompecabezas es un problema de búsqueda, no una fórmula. Cada estado es una asignación de cada disco a una varilla, así que hay 3ⁿ de ellos, y los movimientos legales son las aristas entre ellos; una búsqueda —en anchura, A* o IDA* con una heurística como el número de discos que aún no están en la varilla de destino— encuentra el camino más corto del estado inicial al objetivo. Es un problema de prueba estándar desde el General Problem Solver de Newell, Shaw y Simon, porque es un ejemplo limpio de análisis medios-fines y de descomposición de objetivos: el subobjetivo «mover el disco mayor» solo se alcanza satisfaciendo antes un subobjetivo que parece deshacer el progreso. Ojo: el algoritmo recursivo no es búsqueda; es la solución conocida, y nunca explora un estado que no vaya a usar. El mismo rompecabezas como tarea psicológica.