Calculadora de las Torres de Hanói

Cuánto tiempo es eso en realidad

Las cifras de arriba son exactas y, por sí solas, no enseñan casi nada: pasados unos cuantos miles de millones, un número enorme se parece mucho a otro. Lo que hace la aritmética se ve mejor de lo que se cuenta. Como cada disco que añades duplica el trabajo, una regla con los discos repartidos por igual es una regla con plazos que se multiplican, y toda la distancia entre un descanso para el café (diez discos, diecisiete minutos) y la edad del universo (cincuenta y nueve discos) resulta ser de unos cincuenta pasos.

• 1 disco — 1 movimiento — 1 segundo: el primer tamaño que alcanza un segundo.
• 6 discos — 63 movimientos — 1 minuto: el primer tamaño que alcanza un minuto.
• 12 discos — 4095 movimientos — 1 hora: el primer tamaño que alcanza una hora.
• 17 discos — 131.071 movimientos — 1 día: el primer tamaño que alcanza un día.
• 25 discos — 33.554.431 movimientos — 1 año: el primer tamaño que alcanza un año.
• 32 discos — 4.294.967.295 movimientos — 136 años: el primer tamaño que alcanza una vida humana.
• 38 discos — 274.877.906.943 movimientos — 8,71 mil años: el primer tamaño que alcanza toda la historia escrita.
• 59 discos — 576.460.752.303.423.487 movimientos — 18,3 mil millones de años: el primer tamaño que alcanza la edad del universo.

La franja sombreada de la izquierda es todo lo que puedes jugar aquí de verdad. Once discos son una sesión larga; veinticinco, un año de movimientos sin parar; cincuenta y nueve pasan de la edad del universo. Nada en las reglas cambia a lo largo de ese eje: solo cambia la cuenta.

La fórmula

Una partida perfecta de n discos son exactamente 2ⁿ − 1 movimientos: la fórmula de las Torres de Hanói, que también se escribe 2^n − 1 cuando no hay superíndices a mano. No es lo mejor que ha conseguido nadie, sino un suelo demostrado. Para que el disco mayor pueda moverse siquiera, todos los discos menores tienen que estar apilados fuera del camino en la torre libre, y una vez que ha cruzado han de volver todos encima de él. Dos traslados completos de n − 1 discos, más un movimiento:

T(n) = 2·T(n − 1) + 1, partiendo de T(0) = 0: sin discos, ningún movimiento.

1. 1Mueve los n−1 discos que tiene encima a la torre libre. No puede pasar nada más hasta que estén fuera del camino.

2. 2El disco mayor está libre y su destino, vacío. Cruza en un solo movimiento, el único que necesita esta fase.

3. 3Reconstruye encima de él la pila de n−1 discos. Es el mismo problema otra vez con un disco menos, hasta llegar a un solo disco que se mueve en un paso.

Desarrollarlo da 1, 3, 7, 15, 31, 63: cada uno el doble del anterior más uno, que es la sucesión de los números que están uno por debajo de una potencia de dos. Cada disco que añades duplica con creces el trabajo, y por eso el rompecabezas pasa de un descanso para el café a más de lo que lleva existiendo el universo en menos de cincuenta pasos.

Esa misma recurrencia es el origen de la fama del rompecabezas en los cursos de informática. Como el trabajo se duplica con cada disco, la solución recursiva se ejecuta en tiempo O(2ⁿ), y detrás de eso no se esconde ningún algoritmo más listo: la propia cantidad de movimientos es exponencial y hay que imprimirlos todos. Lo que no cuesta es memoria: la recursión solo baja de disco en disco, así que mantiene O(n) marcos de pila, uno por disco más uno para el caso base: dieciséis en el tablero mayor de aquí, sesenta y cinco en la leyenda. La derivación completa, y por qué esta no es una recurrencia a la que se aplique el Teorema Maestro, está en la página del algoritmo de las Torres de Hanói.

Movimientos mínimos por número de discos

Estos son los tamaños que puedes jugar aquí. La banda de dificultad es la misma que el tablero muestra junto al selector de discos, y cada número de discos enlaza con la lista de movimientos que lo resuelve.

Más allá del tablero

Pasados los 15 discos, el rompecabezas deja de ser algo que se juega y pasa a ser algo que se calcula. Las cifras siguen siendo exactas, pero ya no se pueden alcanzar en una vida humana.

Estos números tienen nombre

Un número que está uno por debajo de una potencia de dos es un número de Mersenne, escrito M_n = 2ⁿ − 1, así que todas las cifras de las tablas de arriba lo son, y el número de movimientos de una partida de las Torres de Hanói nunca es otra cosa. Cuando un número de Mersenne resulta ser primo, es un primo de Mersenne, y esos son los números sobre los que lleva décadas corriendo la búsqueda de primos récord, porque 2ⁿ − 1 es mucho más barato de comprobar que un número cualquiera de su tamaño.

M_n solo puede ser primo cuando n también lo es, pero eso no basta por sí solo, y el contraejemplo es una partida que puedes jugar aquí. Once es primo; sus 2047 movimientos no lo son, porque 2047 = 23 × 89. De los tamaños de este tablero, los discos cuyo número de movimientos es primo son 3, 5, 7 y 13. OEIS A000225 es la sucesión completa.

La leyenda de los sesenta y cuatro discos

El rompecabezas salió a la venta en 1883 y, antes de un año, ya tenía su historia: en un templo de Benarés, unos sacerdotes mueven sesenta y cuatro discos de oro entre tres agujas de diamante, y cuando coloquen el último el mundo se acabará. La aritmética tranquiliza: sesenta y cuatro discos son 18.446.744.073.709.551.615 movimientos y, a un movimiento por segundo, eso son 585 mil millones de años, unas cuarenta veces la edad actual del universo.

Preguntas frecuentes

¿Cuántos movimientos hacen falta en las Torres de Hanói?

El mínimo es 2ⁿ − 1 movimientos para n discos. Tres discos necesitan 7, cinco necesitan 31, diez necesitan 1023 y veinte necesitan 1.048.575. Cada disco de más duplica con creces el total, porque resolver n discos significa resolver n − 1 discos dos veces con un movimiento en medio.

¿Por qué la fórmula es 2ⁿ − 1?

Para mover n discos primero hay que apartar los n − 1 de arriba, después mover una vez el disco mayor y después devolver esos n − 1 encima de él. Eso da T(n) = 2·T(n−1) + 1 con T(1) = 1, y desarrollarlo da 1, 3, 7, 15, 31: cada uno el doble del anterior más uno, que es exactamente 2ⁿ − 1.

¿Cuál es la complejidad temporal de las Torres de Hanói?

O(2ⁿ). Cada disco duplica el trabajo, así que la solución recursiva hace 2ⁿ − 1 movimientos, y ningún algoritmo puede mejorarlo: los movimientos hay que producirlos, y son esos. El espacio es solo O(n): la recursión baja de disco en disco, así que mantiene como mucho n + 1 marcos de pila a la vez, y por eso una llamada de 64 discos agotaría tu paciencia mucho antes que la pila.

¿Cuánto tardarían 64 discos?

Sesenta y cuatro discos necesitan 18.446.744.073.709.551.615 movimientos. A un movimiento por segundo son 585 mil millones de años, mucho más que la edad actual del universo, que es justo el sentido de la leyenda que se le añadió al rompecabezas en 1884.

¿Puede una solución ser más corta que 2ⁿ − 1?

No. 2ⁿ − 1 es un mínimo demostrado, no el mejor resultado conocido: el disco mayor tiene que moverse al menos una vez y, antes de poder hacerlo, todos los discos menores han de estar fuera de él y fuera de su destino. Eso obliga a los dos traslados parciales, y el argumento se repite hasta abajo.

¿Sirve la calculadora para un tablero a medio resolver?

Esta página no: 2ⁿ − 1 da por hecho que todos los discos empiezan en una torre. Para la solución más corta desde una posición que ya está a medio camino, usa el solucionador, que calcula el camino óptimo desde cualquier colocación legal. Abrir el solucionador →