Torres de Hanói — El Enigma Eterno
| Discos | Mín. | Fórmula |
|---|
Las Torres de Hanói es uno de los puzzles matemáticos más elegantes de la historia. Fue inventado en 1883 por el matemático francés Édouard Lucas y esconde una profundidad sorprendente bajo una mecánica muy sencilla.
Tienes N discos apilados en la torre 1, ordenados de mayor (abajo) a menor (arriba). Tu misión es trasladar toda la pila a la torre 3, usando la torre 2 como auxiliar.
Regla 1 — Un disco a la vez: Solo puedes mover el disco que esté en la cima de una torre. Nunca puedes coger discos intermedios o de abajo.
Regla 2 — Nunca el grande sobre el pequeño: No puedes colocar un disco más grande encima de uno más pequeño. El orden siempre debe ser mayor → menor de abajo a arriba.
Regla 3 — Una sola torre de destino: El objetivo es dejar todos los discos en la torre 3 (la última), en el mismo orden original.
En PC: haz clic y arrastra el disco que quieras mover hasta la torre de destino. Las zonas de drop se iluminan en verde (movimiento válido) o rojo (movimiento prohibido).
En móvil: toca el disco superior de cualquier torre y arrástralo con el dedo hasta la torre destino. Suelta cuando estés encima de la columna.
Al inicio del juego, todos los discos están en la torre 1, de mayor a menor. La torre 2 y la torre 3 están vacías. El cronómetro arranca con tu primer movimiento.
Ganas cuando todos los discos están en la torre 3, perfectamente apilados de mayor a menor. Cuantos menos movimientos uses, mayor es tu eficiencia (el juego muestra el mínimo posible).
Vamos a ver cómo resolver el puzzle con 3 discos paso a paso. Los discos están numerados: 1 (pequeño), 2 (mediano), 3 (grande).
Estado inicial:
Estado final (7 movimientos mínimos para 3 discos):
💡 Tip inicial: Empieza siempre por el disco más pequeño. Sigue el patrón: pequeño → siguiente torre, mediano → torre libre, pequeño → encima del mediano. ¡Repite!
Una vez que entiendes las reglas, la pregunta es: ¿cómo llegar al mínimo de movimientos de forma sistemática? Hay varias estrategias y enfoques que transforman la intuición en un plan claro.
La estrategia óptima para 3 torres es siempre recursiva. Hay un único algoritmo que garantiza el mínimo:
Para mover N discos de la torre A a la torre C usando B como auxiliar:
1. Mueve los N-1 discos superiores de A a B (usando C como auxiliar).
2. Mueve el disco más grande de A a C.
3. Mueve los N-1 discos de B a C (usando A como auxiliar).
Este patrón se aplica a sí mismo de forma infinita hasta llegar al caso base (N=1, mueve el disco directamente). Así funciona el botón "Auto" del juego.
Hay una regla de ciclo que describe todos los movimientos óptimos sin calcular nada:
En cada turno impar (1, 3, 5…), mueve el disco más pequeño (disco 1) siempre en la misma dirección cíclica: A→B→C→A→… (o al contrario si el número de discos es par).
En cada turno par (2, 4, 6…), realiza el único movimiento legal que no involucra el disco 1.
Esta es la forma más fácil de jugar sin memorizar nada. Solo tienes que recordar la dirección de rotación del disco pequeño.
↑ Secuencia óptima completa para 3 discos (7 movimientos). Los turnos impares = disco 1, siempre ciclando A→B→C.
Cada movimiento puede identificarse por la posición binaria del disco que se mueve. En el movimiento número k, el disco que debes mover es el que corresponde al bit menos significativo de k.
Movimiento 1 = 001₂ → mueve disco 1
Movimiento 2 = 010₂ → mueve disco 2
Movimiento 3 = 011₂ → mueve disco 1
Movimiento 4 = 100₂ → mueve disco 3
Movimiento 5 = 101₂ → mueve disco 1…
El destino de cada disco depende de su paridad: los discos impares rotan en un sentido, los pares en el contrario. Esto no requiere pensar, solo ejecutar.
En lugar de pensar en todos los discos a la vez, usa este enfoque:
| Fase | Objetivo | Señal visual |
|---|---|---|
| Apertura | Liberar el disco más grande (N) hacia la torre destino | Torre 1 tiene solo disco N abajo |
| Punto medio | Disco N ya está en T3. Reagrupar N-1 discos en T2 | T3 tiene disco N, T2 tiene la sub-pila |
| Final | Colocar N-1 discos sobre el disco N en T3 | T3 se va llenando de mayor a menor |
Con 4 torres (modo disponible en el juego), el algoritmo cambia. El método Frame-Stewart divide la pila en dos grupos: los k discos superiores y los N-k inferiores, y los procesa en paralelo usando las torres extra. Esto reduce drásticamente los movimientos necesarios:
| Discos | Mín. 3 torres | Mín. 4 torres | Ahorro |
|---|---|---|---|
| 4 | 15 | 9 | 40% |
| 5 | 31 | 13 | 58% |
| 6 | 63 | 17 | 73% |
| 7 | 127 | 25 | 80% |
| 8 | 255 | 33 | 87% |
Error 1 — Mover el disco 1 dos veces seguidas: Nunca es óptimo. Señal de que perdiste el hilo del ciclo.
Error 2 — Dejar el disco grande "atrapado": Si el disco más grande no puede moverse a su destino porque las otras torres están ocupadas, hay que reorganizar primero la sub-pila.
Error 3 — Ignorar la paridad del ciclo: Si no recuerdas en qué dirección debe rotar el disco 1, el asistente del juego te lo indica siempre.
💡 El asistente integrado del juego (panel derecho, botón "Mostrar") calcula en tiempo real el siguiente movimiento óptimo y los próximos 3 pasos. Úsalo para aprender el patrón sin tener que memorizar.
Detrás del puzzle más sencillo del mundo se esconde una explosión matemática. Las Torres de Hanói conectan la recursión, la teoría de grafos, los números de Stern-Brocot, la representación binaria y la combinatoria exponencial. Vamos capa a capa.
La fórmula fundamental del juego para 3 torres y N discos es:
Demostración por inducción:
Caso base: T(1) = 1 movimiento = 2¹ − 1 = 1 ✓
Paso inductivo: Para mover N discos necesitas:
· T(N−1) movimientos para llevar la sub-pila a la torre auxiliar.
· 1 movimiento para el disco más grande.
· T(N−1) movimientos para llevar la sub-pila al destino.
Total: T(N) = 2·T(N−1) + 1 = 2·(2^(N−1) − 1) + 1 = 2^N − 1 ✓
Esta relación de recurrencia es la clave: cada disco añadido duplica el trabajo anterior y añade uno más. Es crecimiento exponencial puro.
Ejemplo real: con 8 discos en el juego necesitas 255 movimientos mínimos. Con 64 discos (la leyenda de Brahma), serían 2⁶⁴ − 1 ≈ 1.8 × 10¹⁹ movimientos. A 1 movimiento por segundo, eso es más de 580 mil millones de años.
El estado de cada disco puede codificarse en binario. En el movimiento número k (empezando por 1), el disco que se mueve es el correspondiente al trailing zero count de k más uno, o de forma equivalente, al bit menos significativo de k:
Donde v₂(k) es la 2-valuación p-ádica de k, es decir, el mayor exponente de 2 que divide a k.
Ejemplo: k=4=100₂ → v₂(4)=2 → se mueve el disco 3 (el tercero). Con esta fórmula puedes predecir el movimiento número 42 sin simular nada: 42 = 101010₂ → v₂(42)=1 → se mueve el disco 2.
El espacio de estados de Hanói forma un grafo de Sierpiński. Cada estado posible (configuración de los discos) es un nodo, y cada movimiento legal es una arista. Para N discos:
Para N=3: 27 estados posibles. Para N=4: 81 estados. El grafo tiene estructura autosimilar: el grafo de N discos contiene 3 copias del grafo de N−1 discos, conectadas por 3 aristas.
La ruta óptima de inicio a fin tiene longitud 2^N − 1 y pasa exactamente por el diámetro del grafo (la mayor distancia posible entre dos nodos). ¡El problema más difícil coincide con la distancia máxima del grafo!
Con p = 4 torres, el mínimo teórico sigue sin estar demostrado formalmente (es uno de los problemas abiertos más famosos de la combinatoria). La conjetura de Frame-Stewart da el algoritmo más conocido:
Con F(1,4) = 1. El valor de k óptimo es aproximadamente k ≈ N − ⌈√(2N)⌉. Esto produce los valores:
| N | F(N,3) = 2ᴺ−1 | F(N,4) conjetura | k óptimo |
|---|---|---|---|
| 3 | 7 | 5 | 1 |
| 4 | 15 | 9 | 2 |
| 5 | 31 | 13 | 2 |
| 6 | 63 | 17 | 3 |
| 7 | 127 | 25 | 3 |
| 8 | 255 | 33 | 4 |
La secuencia 1, 3, 5, 9, 13, 17, 25, 33… (OEIS A007664) crece polinomialmente frente al exponencial de 3 torres.
La secuencia de movimientos de Hanói está biyectivamente relacionada con el código Gray de N bits. El código Gray es una secuencia de números binarios en la que dos valores consecutivos difieren en exactamente un bit. Cada cambio de bit corresponde a mover el disco de ese número:
Gray(0) = 000 → start
Gray(1) = 001 → mueve disco 1
Gray(2) = 011 → mueve disco 2
Gray(3) = 010 → mueve disco 1
Gray(4) = 110 → mueve disco 3
Gray(5) = 111 → mueve disco 1…
Esta correspondencia significa que resolver Hanói es equivalente a enumerar todos los números de N bits en código Gray. El juego es, en esencia, un enumerador de Gray.
El algoritmo recursivo tiene complejidad temporal exponencial O(2ᴺ) — no hay forma de hacerlo más rápido para 3 torres. La espacial es lineal O(N) por la pila de llamadas recursivas (profundidad N).
Un movimiento es dominante si acerca el estado actual a la solución en el grafo de Sierpiński. Matemáticamente, en cada paso existe exactamente un movimiento óptimo (salvo al inicio donde hay dos opciones simétricas). Esto se demuestra porque el grafo de Hanói es un árbol de Cayley con estructura única.
Consecuencia práctica: si llevas K movimientos extra respecto al óptimo, necesitarás al menos 2K movimientos adicionales para volver al camino óptimo (debes deshacer cada error con dos movimientos correctivos). El coste de cada error se duplica.
Esto explica por qué el asistente del juego calcula el óptimo desde el estado actual, no desde el inicio: el camino más corto hacia la meta desde cualquier configuración válida es siempre calculable con el mismo algoritmo recursivo.
Según la leyenda que Lucas usó para comercializar el puzzle, los sacerdotes del templo de Benarés mueven 64 discos de oro desde el alba de los tiempos. Cuando terminen, el mundo acabará. El número de movimientos requerido es:
A razón de 1 movimiento por segundo, esto tardaría aproximadamente 585 mil millones de años — unas 42 veces la edad del universo. La matemática convierte un juguete sencillo en infinito.