Torres de Hanói: solución, fórmula 2^n - 1 y las matemáticas del juego
Respuesta corta: las Torres de Hanói con n discos y tres varillas necesitan como mínimo 2n − 1 movimientos: 7 con 3 discos, 15 con 4, 31 con 5, 127 con 7. Para resolverlas, pasa los n − 1 discos de arriba a la varilla libre, el disco más grande a la de destino y después los n − 1 discos encima, que es el mismo rompecabezas, solo que más pequeño. La regla rápida: mueve el disco más pequeño cada dos movimientos, siempre en el mismo sentido, y entre medias haz el único otro movimiento legal. El juego lo inventó Édouard Lucas en 1883.
Las Torres de Hanói parecen un juguete: tres varillas y una pila de discos que se estrechan hacia arriba. Hay que pasar toda la pila a otra varilla, disco a disco, sin poner nunca uno grande sobre uno pequeño. Con 3 discos se tarda un minuto. Con 7 hace falta concentración. Con 64 duraría más que el Sol. Detrás de este rompecabezas tan sencillo hay uno de los ejemplos más limpios de recursividad de las matemáticas, un contador binario escondido y un fractal. Primero la solución, después las matemáticas.
Las reglas
- Hay tres varillas. Al principio todos los discos están en una, el más grande abajo.
- Se mueve un disco cada vez: el de arriba de cualquier varilla pasa a otra varilla.
- Nunca se puede poner un disco sobre otro más pequeño.
- El rompecabezas está resuelto cuando toda la torre está en la varilla de destino en el mismo orden.
En nuestro juego Torres de Hanói la torre empieza en la varilla izquierda y debe acabar en la derecha. El nivel fácil tiene 3 discos, el medio 5 y el difícil 7. No hay límite de tiempo, y el juego muestra junto a tus movimientos el mínimo posible.
La solución con 3 discos, movimiento a movimiento
Llamemos a las varillas A (inicio, izquierda), B (centro) y C (destino, derecha), y a los discos 1 (pequeño), 2 (mediano) y 3 (grande). La solución más corta tiene 7 movimientos:
| Mov. | Disco | De → a | Después (A | B | C) |
|---|---|---|---|
| 1 | 1 | A → C | 3 2 | – | 1 |
| 2 | 2 | A → B | 3 | 2 | 1 |
| 3 | 1 | C → B | 3 | 2 1 | – |
| 4 | 3 | A → C | – | 2 1 | 3 |
| 5 | 1 | B → A | 1 | 2 | 3 |
| 6 | 2 | B → C | 1 | – | 3 2 |
| 7 | 1 | A → C | – | – | 3 2 1 |
Fíjate en la estructura. Los movimientos 1 a 3 pasan una torre de dos discos de A a B. El 4 mueve el disco grande. Los movimientos 5 a 7 colocan la torre de dos discos de B encima de él. Ahí está todo el secreto.
Dos formas de resolver cualquier torre
1. El método recursivo (pensar en torres)
Para pasar una torre de n discos de la varilla de inicio a la de destino:
- Pasa los n − 1 discos de arriba del inicio a la varilla libre (usando la de destino como auxiliar).
- Pasa el disco más grande del inicio al destino.
- Pasa los n − 1 discos de la varilla libre al destino (usando la de inicio como auxiliar).
Los pasos 1 y 3 son el mismo rompecabezas con un disco menos, así que se les aplican los mismos tres pasos, y así sucesivamente hasta llegar a un solo disco, que simplemente se mueve. Por eso las Torres de Hanói son el primer ejemplo clásico de recursividad en los cursos de programación: una función que resuelve un problema llamándose a sí misma con una versión más pequeña. También es la mejor forma de entender cualquier posición: pregúntate cuál es el disco más grande que aún no está en su sitio; todo lo que tiene encima debe ir a la tercera varilla.
2. El método iterativo (sin planificar)
- En cada movimiento impar (1.º, 3.º, 5.º...), mueve el disco más pequeño una varilla, siempre en el mismo sentido. Con un número impar de discos el sentido es A → C → B → A (inicio, destino, centro); con un número par, A → B → C → A.
- En cada movimiento par, haz el único movimiento legal que no toca el disco más pequeño. Siempre hay exactamente uno.
Siguiendo estas dos reglas terminarás en el mínimo de movimientos sin pensar por adelantado. Así resuelve la mayoría de la gente 7 discos. El método recursivo es el que enseña por qué funciona.
Por qué el mínimo es 2n − 1
Sea T(n) el mínimo de movimientos para n discos. El disco más grande tiene que moverse al menos una vez. En ese momento debe estar solo en su varilla y la de destino debe estar vacía, así que los otros n − 1 discos tienen que estar apilados en la tercera varilla: eso costó al menos T(n − 1) movimientos. Después, esos discos aún tienen que ponerse encima de él: otra vez al menos T(n − 1). Por tanto,
T(n) = 2 × T(n − 1) + 1, con T(1) = 1.
Eso da 1, 3, 7, 15, 31, 63, 127... y cada número es uno menos que una potencia de dos: T(n) = 2n − 1. El método recursivo consigue exactamente ese número, así que es óptimo, y la solución más corta es además única: solo hay una manera de hacerlo en 2n − 1 movimientos.
Lo rápido que crece
| Discos | Mínimo de movimientos | A un movimiento por segundo |
|---|---|---|
| 3 | 7 | 7 segundos |
| 4 | 15 | 15 segundos |
| 5 | 31 | medio minuto |
| 6 | 63 | 1 minuto |
| 7 | 127 | unos 2 minutos |
| 8 | 255 | unos 4 minutos |
| 10 | 1.023 | unos 17 minutos |
| 20 | 1.048.575 | unos 12 días |
| 32 | 4.294.967.295 | unos 136 años |
| 64 | 18.446.744.073.709.551.615 | unos 585.000 millones de años |
Cada disco añadido duplica el trabajo. Así es el crecimiento exponencial, y por eso este rompecabezas se usa para enseñarlo.
Patrones escondidos
Qué disco se mueve cuándo: un contador binario
En la solución más corta, el disco k (contando desde el más pequeño) se mueve exactamente 2n−k veces. El más pequeño hace la mitad de todos los movimientos (redondeando hacia arriba) y el más grande se mueve una sola vez, justo en la mitad: tras 3 movimientos con 3 discos, tras 15 con 5, tras 63 con 7.
Hay una regla todavía más elegante. Escribe el número del movimiento en binario y cuenta los ceros finales: el movimiento 1 es 1 (ningún cero, disco 1), el 2 es 10 (un cero, disco 2), el 3 es 11 (disco 1), el 4 es 100 (dos ceros, disco 3). Siempre se mueve el disco cuyo número es uno más que la cantidad de ceros finales. La solución es literalmente un contador binario de 0 a 2n − 1, y el número del movimiento basta para saber qué disco mover. Esa misma secuencia (1, 2, 1, 3, 1, 2, 1...) es el orden en que cambian los bits en el código Gray, una forma de contar en binario en la que en cada paso cambia un solo bit.
Un fractal: el triángulo de Sierpiński
Cada disco puede estar en cualquiera de las tres varillas, y el orden en cada varilla viene impuesto (el más grande abajo), así que hay exactamente 3n posiciones legales: 27 con 3 discos, 2.187 con 7. Si dibujas cada posición como un punto y unes dos puntos cuando un movimiento legal lleva de una a otra, sale un triángulo formado por tres triángulos más pequeños, cada uno formado por otros tres: una versión del triángulo de Sierpiński. Las tres esquinas son las posiciones con toda la torre en una varilla, y la solución más corta recorre en línea recta uno de los lados.
Nuestros tres niveles son números primos
Los números de la forma 2n − 1 se llaman números de Mersenne. Algunos son primos, y lo son los mínimos de movimientos de nuestros tres niveles: 7, 31 y 127. El último enlaza con el inventor del juego: en 1876 Édouard Lucas demostró que 2127 − 1, un número de 39 cifras, es primo. Fue el mayor primo conocido durante 75 años, hasta 1951, y el test de Lucas-Lehmer, basado en su método, se sigue usando hoy para encontrar primos récord.
Cuatro varillas: un problema mucho más difícil
Con una cuarta varilla la torre se puede mover mucho más rápido, porque hay más sitios donde dejar discos. La versión de cuatro varillas la publicó Henry Dudeney en The Canterbury Puzzles (1907) como «The Reve's Puzzle». En 1941 J. S. Frame y B. M. Stewart propusieron, por separado, un método: pasar algunos discos de arriba a una varilla libre usando las cuatro varillas, mover el resto con las tres que quedan y volver a poner el primer grupo encima. La mejor división da estos números de movimientos:
| Discos | 3 varillas | 4 varillas (Frame-Stewart) |
|---|---|---|
| 3 | 7 | 5 |
| 4 | 15 | 9 |
| 5 | 31 | 13 |
| 6 | 63 | 17 |
| 7 | 127 | 25 |
| 8 | 255 | 33 |
| 10 | 1.023 | 49 |
Durante más de 70 años nadie pudo demostrar que ese método fuera el mejor posible con cuatro varillas. Lo demostró por fin Thierry Bousch en 2014. Con cinco o más varillas la pregunta sigue abierta, algo notable para un rompecabezas que se vendía como juguete en 1883.
Historia: Lucas, un seudónimo y una leyenda
El rompecabezas apareció en París en 1883, atribuido al «profesor N. Claus de Siam», del «colegio Li-Sou-Stian». Los dos nombres son anagramas: N. Claus de Siam es Lucas d'Amiens, y Li-Sou-Stian es Saint Louis, el liceo Saint-Louis donde Édouard Lucas enseñaba matemáticas. Lucas (1842-1891) es conocido también por los números de Lucas, primos hermanos de la sucesión de Fibonacci, y por una colección de recreaciones matemáticas en cuatro tomos.
El juego venía con una leyenda: en un gran templo, unos sacerdotes trasladan una torre de 64 discos de oro entre tres agujas de diamante siguiendo las mismas dos reglas, y cuando terminen llegará el fin del mundo. Como muestra la tabla de arriba, incluso a un movimiento por segundo y sin errores necesitarían unos 585.000 millones de años, más de 40 veces la edad del universo. La leyenda, como el nombre de Hanói, formaba parte del envoltorio exótico de Lucas y no es una tradición antigua.
Dónde se usan hoy las Torres de Hanói
- Enseñanza de la programación. Es el ejercicio clásico de recursividad; el método de tres pasos se convierte en una función de pocas líneas.
- Enseñanza de las matemáticas. Relaciones de recurrencia, inducción matemática, crecimiento exponencial y números binarios en un solo rompecabezas.
- Psicología. Las tareas de torres sirven para estudiar la planificación y la resolución de problemas: cuántos pasos piensa alguien por adelantado. Una variante, la Torre de Londres, propuesta por Tim Shallice en 1982, se usa en evaluación neuropsicológica.
- Copias de seguridad. El esquema de rotación de cintas «Torres de Hanói» usa el mismo patrón 1, 2, 1, 3, 1, 2, 1 para decidir qué cinta sobrescribir, de modo que los últimos días quedan cubiertos con detalle y los periodos antiguos cada vez con menos.
Consejos para nuestro juego
- Empieza en el nivel fácil y resuelve 3 discos con la regla iterativa hasta que salga sola; después pasa al método recursivo con 5 discos.
- Con un número impar de discos (todos nuestros niveles: 3, 5, 7), el primer movimiento es el disco más pequeño a la varilla derecha.
- Comprueba la mitad del camino: cuando se mueve el disco más grande, todos los demás deben estar en la varilla central.
- Nunca muevas el disco más pequeño dos veces seguidas; siempre es un movimiento perdido.
- La puntuación es 1.000 × mínimo de movimientos ÷ tus movimientos, multiplicado por 1, 2 o 4 según el nivel, así que una torre de 7 discos perfecta da 4.000 puntos. Deshacer un movimiento cuenta como un movimiento.
Si te gustan los rompecabezas en los que compensa planificar varios pasos, prueba también Empuja cajas (una variante del Sokoban; mira cómo resolver Sokoban) y el Puzzle deslizante.
Preguntas frecuentes
¿Cuántos movimientos se necesitan como mínimo en las Torres de Hanói?
Con n discos y tres varillas, el mínimo es 2 elevado a n, menos 1: 7 movimientos para 3 discos, 15 para 4, 31 para 5, 63 para 6 y 127 para 7. Cada disco más duplica los movimientos y suma uno.
¿Cómo se resuelven las Torres de Hanói con 3 discos?
Con las varillas A (inicio), B (centro) y C (destino): disco pequeño de A a C, mediano de A a B, pequeño de C a B, grande de A a C, pequeño de B a A, mediano de B a C y pequeño de A a C. Son 7 movimientos, el mínimo.
¿Cuál es el truco de las Torres de Hanói?
En cada movimiento impar, mueve el disco más pequeño una varilla, siempre en el mismo sentido (primero hacia la varilla de destino si el número de discos es impar, hacia la central si es par). En cada movimiento par, haz el único movimiento legal que no afecta al disco más pequeño.
¿Cuánto se tardaría con 64 discos?
2 elevado a 64, menos 1, es decir 18.446.744.073.709.551.615 movimientos. A un movimiento por segundo y sin un solo error, unos 585.000 millones de años, alrededor de 40 veces la edad actual del universo.
¿Quién inventó las Torres de Hanói?
El matemático francés Édouard Lucas, que lo vendió en 1883 con el seudónimo N. Claus de Siam, anagrama de Lucas d'Amiens. Lo acompañó de la leyenda de unos sacerdotes que mueven 64 discos de oro, tras lo cual llegaría el fin del mundo.
