Tres postes, una torre de discos y muy pocas reglas: la Torre de Hanói es un juego en el que planificar importa más que la velocidad. También es un ejemplo concreto de recursión: resolver un problema utilizando la solución del mismo problema, pero más pequeño.
Abrir el laboratorio de la Torre de Hanói: juega con 1 a 10 discos
Prueba primero con pocos discos y después compara tu recorrido con la solución animada.
Objetivo y reglas del juego
Los postes se llaman A, B y C. Al principio todos los discos están en A, del mayor abajo al menor arriba. Debes trasladar toda la torre a C; B sirve como apoyo temporal.
- Mueve un solo disco cada vez.
- Solo puedes tomar el disco superior de un poste.
- Nunca coloques un disco grande sobre otro más pequeño. Un poste vacío puede recibir cualquier disco.
Numeramos los discos desde el menor, 1, hasta el mayor, n. En los ejemplos, las listas se leen de abajo arriba: [3, 2, 1] es la torre completa y [] un poste vacío. Un movimiento traslada un disco; cada clic de la interfaz no cuenta por separado.
Empecemos por el caso más sencillo
Un disco: basta un movimiento
El disco 1 va directamente de A a C. No hay nada que despejar: es el caso no vacío más pequeño del juego.
Dos discos: primero libera el grande
No puedes mover inmediatamente el disco 2 porque el disco 1 está encima. Estos son los tres movimientos necesarios:
- Disco 1: A → B.
- Disco 2: A → C.
- Disco 1: B → C.
El poste auxiliar no es un destino final: sirve para despejar el disco que quieres mover.
Tres discos: los siete movimientos
Para liberar el disco 3, traslada primero la pequeña torre [2, 1] de A a B utilizando C como apoyo. Después lleva el disco 3 a C y finalmente reconstruye [2, 1] encima. El procedimiento para dos discos es el mismo, pero los postes intercambian sus funciones.
| Movimiento | Disco | Traslado | A | B | C |
|---|---|---|---|---|---|
| 0 | — | Inicio | [3, 2, 1] | [] | [] |
| 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] |
La fila 0 describe el inicio: no es un movimiento. De la fila 1 a la 7, cada fila traslada exactamente un disco respetando todas las reglas.
La estrategia general: un problema dentro del problema
Supongamos que ya sabes trasladar una torre de n−1 discos. Para trasladar n de A a C:
- Lleva los n−1 discos superiores de A a B, utilizando C como apoyo.
- Mueve el disco n de A a C.
- Lleva los n−1 discos de B a C, utilizando A como apoyo.
![Tres posiciones sucesivas: A=[3], B=[2,1]; después B=[2,1], C=[3]; finalmente C=[3,2,1]. Los postes no indicados están vacíos.](/assets/images/editorial/hanoi-recursion-stages.svg)
«Trasladar n−1 discos» no significa moverlos en bloque: repite esta misma receta con un disco menos hasta llegar al caso más sencillo. Cada movimiento efectivo sigue trasladando un solo disco.
Este pseudocódigo explicita las funciones de los postes. Con cero discos no hay nada que mover: esa condición detiene las llamadas recursivas.
Hanoi(n, origen, destino, apoyo):
si n = 0: terminar
Hanoi(n−1, origen, apoyo, destino)
mover el disco n de origen a destino
Hanoi(n−1, apoyo, destino, origen)La llamada inicial es Hanoi(n, A, C, B). Cada llamada cambia las funciones de origen, destino y apoyo, no las reglas del juego.
¿Por qué no se puede mejorar 2ⁿ − 1?
Llamemos M(n) al mínimo de movimientos para trasladar una torre completa de n discos entre dos postes. Antes de mover por primera vez el disco mayor, todos los demás deben estar juntos en el tercer poste: hacen falta al menos M(n−1) movimientos. El disco mayor requiere al menos uno. Después de su última llegada al poste final, los discos pequeños deben trasladarse desde el tercer poste hasta quedar encima: al menos otros M(n−1) movimientos. Los desvíos no eliminan estos dos traslados obligatorios.
La estrategia descrita realiza exactamente estas tres etapas sin movimientos adicionales. Por tanto, alcanza ese límite:
M(0) = 0
M(n) = 2 × M(n−1) + 1 = 2n − 1
Para comprobar la última igualdad, sustituye M(n−1) por 2n−1 − 1: resulta 2 × (2n−1 − 1) + 1 = 2n − 1. El caso base M(0) = 0 completa el razonamiento por inducción.
| Discos | Mínimo de movimientos |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
| 9 | 511 |
| 10 | 1023 |
Un disco más casi duplica el trabajo. A un movimiento por segundo, 10 discos requieren 1023 segundos, es decir, 17 minutos y 3 segundos, sin pausas. El número de movimientos crece exponencialmente: una regla breve puede describir un procedimiento muy largo.
Cómo utilizar el laboratorio
Entrar en el laboratorio interactivo de la Torre de Hanói
- Elige entre 1 y 10 discos: todos los niveles están disponibles desde el inicio.
- Toca el poste de origen y después el de destino. Con teclado utiliza Tab, Intro o Espacio.
- «Deshacer movimiento» revierte el último traslado; «Reiniciar nivel» permite empezar desde cero.
- «Pista» sugiere sin mover; «Un paso» ejecuta un movimiento; «Iniciar solución» anima el recorrido a la velocidad elegida.
- La solución guiada continúa desde la posición actual, incluso después de un recorrido distinto del tuyo. «Pausa» deja terminar el movimiento que ya haya empezado.
«Mínimo desde el inicio» se refiere a la torre inicial; «Mínimo aún necesario», a la posición actual. Tras un desvío, los movimientos realizados más los que faltan pueden superar el mínimo inicial. Los récords solo se actualizan en partidas manuales sin ayuda y permanecen en este navegador: no se envían al sitio.
Tres retos antes de revelar las respuestas
1. ¿Cuál es el mínimo de movimientos para cuatro discos?
Mostrar la solución explicada
Tres discos necesitan 7 movimientos. Cuatro necesitan 7 para liberar el disco 4, uno para moverlo y 7 para reconstruir la torre: 7 + 1 + 7 = 15. La fórmula también da 2⁴ − 1 = 15.
2. Con tres discos que van de A a C, ¿por qué conviene empezar moviendo el disco 1 de A a C y no de A a B?
Mostrar la solución explicada
Primero debes trasladar [2, 1] de A a B. Para hacerlo en tres movimientos, el disco 1 va a C, el disco 2 a B y el disco 1 a B. Empezar por A → B está permitido, pero no permite completar toda la torre en el mínimo de 7 movimientos.
3. Has realizado 4 movimientos y el laboratorio indica que necesitas al menos otros 5. ¿Puedes terminar en 7 movimientos en total?
Mostrar la solución explicada
No: el mejor total posible desde esta posición es 4 + 5 = 9. La solución guiada optimiza el recorrido restante, pero no borra los movimientos ya realizados. Deshaz un desvío o reinicia para intentar alcanzar el mínimo inicial.
¿Qué enseña este juego?
La Torre de Hanói muestra cómo descomponer una tarea, reconocer un subproblema y definir una condición de parada. La recursión no es un truco para saltarse pasos: es una forma precisa de organizarlos respetando la misma restricción en cada movimiento.
Referencia para las reglas, la estrategia recursiva y el mínimo de movimientos: NIST — Dictionary of Algorithms and Data Structures: Towers of Hanoi.