Torres de Hanói

Juega a las Torres de Hanói en línea

El tablero de arriba es un juego gratuito de las Torres de Hanói que funciona en tu navegador: nada que descargar, ninguna cuenta que crear. Elige entre 3 y 15 discos y mueve la pila entera de la torre izquierda a la derecha.

• Móvil o tableta: toca una torre para levantar su disco superior y toca otra para soltarlo.
• Ratón: arrastra un disco, o haz clic en una torre y después en otra.
• Teclado: ← y → eligen torre, ↑ levanta y ↓ suelta; 1, 2 y 3 van directamente a las torres A, B y C, y Esc devuelve el disco.

Equivocarse no cuesta nada. Deshacer retira tu último movimiento, Reiniciar empieza otra vez con el mismo tamaño y Pista levanta el disco que movería la solución más corta y dice adónde va. Paso lo juega por ti. Y si prefieres mirar, Resolución automática termina el rompecabezas desde donde esté el tablero, no solo desde el principio.

No se cuenta nada hasta que mueves. Después de tu primer movimiento el panel muestra:

• tus jugadas, un cronómetro y una puntuación de eficiencia: tu partida como porcentaje de una perfecta;
• si sigues en el camino óptimo o cuántos movimientos te has apartado de él.

La línea de tiempo bajo el tablero guarda la partida entera. Vuelve a cualquier posición anterior o reprodúcela a 0,5×, 1×, 2× o 4×; la misma velocidad marca el ritmo de la Resolución automática. El modo concentración aparta todo menos las torres, y la página recuerda con cuántos discos jugaste la última vez. Al terminar, la pantalla de resultado compara tus movimientos con el mínimo y te ofrece un disco más.

El problema de las Torres de Hanói

El problema de las Torres de Hanói empieza con tres torres y una pila de discos de distintos tamaños en una de ellas, el mayor abajo. El objetivo es mover la pila entera a otra torre bajo tres reglas:

1. Se mueve un disco a la vez.
2. Solo puede moverse el disco superior de una torre.
3. Un disco mayor nunca puede quedar sobre uno menor.

Ese es todo el rompecabezas, y se aprende en un minuto. La tercera regla es lo que lo hace difícil: cada disco tiene que esperar en algún sitio legal mientras se mueven los de debajo, y con solo tres torres nunca sobra sitio. Cómo jugar a las Torres de Hanói las muestra en imágenes, con un tablero de práctica y un ejemplo resuelto.

El matemático francés Édouard Lucas publicó el rompecabezas en 1883. Un año después, un artículo de revista que lo presentaba añadió la leyenda que lo hizo famoso: sacerdotes brahmanes moviendo sesenta y cuatro discos de oro, y el fin del mundo cuando terminaran. A un movimiento por segundo, eso llevaría unos 585 000 millones de años.

Movimientos mínimos y la fórmula 2ⁿ − 1

El número mínimo de movimientos de unas Torres de Hanói con n discos es 2ⁿ − 1, que también se escribe 2^n − 1. Tres discos necesitan 7 movimientos, cuatro necesitan 15 y con 5 discos hacen falta como mínimo 31. Es un suelo demostrado, no un récord: no existe ninguna solución más corta para ningún tamaño, y es el número contra el que te mide la puntuación de eficiencia del tablero.

La ecuación detrás de la fórmula

La ecuación sale directamente de las reglas. Antes de que el disco mayor pueda moverse, los n − 1 discos que tiene encima han de estar apilados en la torre libre; luego cruza; luego esos discos vuelven encima de él. Escribiendo T(n) para el menor número de movimientos que hace todo eso:

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

Cada tamaño cuesta el doble que el de debajo, más uno: 1, 3, 7, 15, 31, 63. Todos ellos son uno menos que una potencia de dos, y de ahí viene la forma cerrada T(n) = 2ⁿ − 1. La demostración de que 2ⁿ − 1 es el mínimo trabaja las dos mitades de esa afirmación —por qué esa cantidad de movimientos siempre basta y por qué menos es imposible— y la calculadora de movimientos mínimos da la cifra exacta para cualquier número de discos hasta sesenta y cuatro.

Movimientos mínimos según el número de discos

Cada tamaño enlaza con su solución completa, con todos los movimientos listados y jugados en un tablero. La partida más grande aquí es de 15 discos, o 32.767 movimientos: cada disco que añades duplica la longitud de la partida, más un movimiento.

El algoritmo de las Torres de Hanói y la recursión

La ecuación de arriba es también el algoritmo, leído como instrucciones. Para mover n discos de una torre de origen a una de destino:

1. Mueve n − 1 discos del origen a la torre libre.
2. Mueve el disco mayor del origen al destino.
3. Mueve los n − 1 discos de la torre libre al destino.

Los pasos 1 y 3 son el mismo problema con un disco menos, así que el algoritmo los resuelve llamándose a sí mismo, y una llamada sin discos que mover simplemente termina. Eso es la recursión de las Torres de Hanói al completo, y por eso casi todos los cursos de informática usan este rompecabezas para enseñar recursión. El truco es no intentar imaginar todos los movimientos a la vez: confía en que la llamada más pequeña hará su trabajo, y los tres pasos son la solución entera.

Como el algoritmo hace exactamente 2ⁿ − 1 movimientos, su tiempo de ejecución es O(2ⁿ), y nada puede mejorarlo: cada uno de esos movimientos hay que hacerlo. Su uso de memoria es solo O(n). La página del algoritmo de las Torres de Hanói ejecuta el código línea a línea junto a un tablero en vivo y dibuja el árbol de llamadas sobre la marcha, y la solución iterativa produce los mismos movimientos con dos reglas y un bucle.

Torres de Hanói en Python, Java y otros lenguajes

Los tres pasos se traducen casi palabra por palabra a código. Torres de Hanói en Python es una función de siete líneas: un caso base para cero discos, dos llamadas recursivas y la línea entre ellas que imprime un movimiento. Torres de Hanói en Java es el mismo método dentro de una clase, y el sitio donde averiguar por qué la cuenta de sesenta y cuatro discos no cabe en un long. También hay programas completos en C, C++, C# y JavaScript.

Todos los listados se han ejecutado y su salida se ha comprobado contra el solucionador de este sitio, y cada uno viene con una explicación que dice por qué está ahí cada línea, no qué hace la sintaxis.

Más formas de jugar y de aprender

Cuando tres torres y una pila completa te resulten fáciles, hay más que probar:

• El reto diario: una posición desordenada, la misma para todos, nueva a medianoche UTC. Resuélvela sin el solucionador para mantener la racha.
• El solucionador: todos los movimientos de la solución más corta desde cualquier posición legal, incluida aquella en la que estás atascado en este tablero.
• Estrategias: la única idea que se repite detrás de cada tamaño, y una regla que te dice el siguiente movimiento sin planear.
• Variantes: cuatro torres en lugar de tres, un anillo donde los discos viajan en un solo sentido, dos colores que ordenar y una posición inicial al azar.
• Para docentes: un plan de clase de 45 minutos, una ficha imprimible con soluciones y un tablero para incrustar en una página de curso.

Preguntas frecuentes

¿Qué son las Torres de Hanói?

Las Torres de Hanói son un rompecabezas con tres torres y una pila de discos de distintos tamaños. Hay que mover la pila entera de una torre a otra, un disco cada vez, y un disco mayor nunca puede descansar sobre uno menor. Lo publicó el matemático francés Édouard Lucas en 1883.

¿Puedo jugar gratis a las Torres de Hanói en línea?

Sí. El tablero de esta página es gratuito, funciona en cualquier navegador moderno de móvil, tableta u ordenador, y no necesita descarga ni cuenta. El número de discos con el que jugaste por última vez y tus mejores puntuaciones se guardan en tu propio navegador, no en un servidor.

¿Cuál es el número mínimo de movimientos en las Torres de Hanói?

Una partida perfecta de n discos son 2ⁿ − 1 movimientos. Tres discos necesitan 7, cinco necesitan 31 y 15 discos necesitan 32.767. No existe ninguna solución más corta, así que ese número es un suelo firme, no solo un objetivo.

¿Cómo se resuelven las Torres de Hanói?

Toda solución es la misma idea repetida: para mover una pila de n discos al destino, primero aparta los n − 1 discos de arriba a la torre libre, cruza el disco mayor y después trae esos n − 1 discos encima de él. La pila más pequeña obedece exactamente la misma regla, y por eso un solo método resuelve todos los tamaños.

¿Hay un atajo para saber el siguiente movimiento?

Sí. En cada movimiento impar, mueve el disco más pequeño una torre en una dirección fija: a la izquierda si el número de discos es impar, a la derecha si es par, dando la vuelta en los extremos; con tres discos, su primer movimiento da la vuelta de A a C. En cada movimiento par, haz el único movimiento legal que no toca al disco más pequeño. Alternando los dos se juega una partida perfecta sin planear nada.

¿Con cuántos discos puedo jugar aquí?

Puedes jugar con 3 a 15 discos. Empieza con 3 para aprender la forma de la solución y después añade uno cada vez: cada disco que añades duplica aproximadamente el trabajo.

¿Puedo deshacer un movimiento o repetir mi partida?

Sí. Hay un botón de deshacer, y cada partida guarda además una línea de tiempo completa: vuelve a cualquier posición anterior y el tablero muestra exactamente ese estado, o reproduce tu partida a cuatro velocidades para ver dónde te saliste del camino óptimo.