Torre de Hanói

El rompecabezas tiene tres varillas y una pila de discos de tamaños distintos, ensartados en la varilla de origen, la A, con el mayor abajo. El objetivo es llevar la pila entera a la varilla de destino, la C, con ayuda de la varilla auxiliar, la B. Las reglas son solo tres, y el juego no deja saltarse ninguna.

• Un solo disco por movimiento.
• Solo se mueve el disco superior de una varilla, el que queda arriba del todo.
• Nunca se pone un disco mayor sobre uno menor. En una varilla vacía puede ir cualquiera.

Para mover, toca o haz clic en una varilla y su disco superior se levanta; después toca la varilla donde quieres dejarlo. También puedes arrastrar el disco. Con el teclado, llega a una varilla con el tabulador y pulsa su número o su letra para levantar y para soltar. Escape devuelve el disco levantado y las flechas pasan de una varilla a otra.

Si un movimiento rompe una regla, el tablero tiembla y explica el motivo, por ejemplo «El disco 2 no puede ir sobre el disco 1». Con la reducción de movimiento activada, solo aparece el aviso.

Tres contadores siguen la partida. «Movimientos» cuenta los movimientos hechos, y deshacer resta uno. «Mínimo posible» da el menor número posible desde el inicio de la partida, y «Tiempo» corre desde el primer movimiento hasta que la torre queda completa. Deshacer no tiene límite, y cada movimiento deshecho queda anotado en el resultado.

La primera partida trae 4 discos en tres varillas, que piden 15 movimientos como mínimo. Puedes elegir de 3 a 10 discos, o cuatro varillas con hasta 8 discos y la meta en la D. Con cuatro, las pistas recorren las 65.536 posiciones de 8 discos, y con más discos tardarían demasiado en un móvil.

Hacen falta 2^n - 1 movimientos como mínimo: 7 con 3 discos, 15 con 4, 31 con 5 y 1023 con 10. A un movimiento por segundo, sin pausas ni errores, la torre de 10 discos lleva 17 min 3 s.

Con 7 discos la cuenta sube a 127 movimientos, algo más de 2 minutos a ese ritmo, y con 8, el tamaño del juego original de Lucas, a 255. Lucas ya escribió que eso supone más de 4 minutos. Cada fila duplica la anterior más uno, de modo que el tiempo se dispara enseguida.

La última columna cuenta las maneras de repartir los discos: cada uno puede estar en cualquiera de las tres varillas, así que hay 3^n posiciones posibles, 243 con 5 discos. Las cifras de 3, 8 y 10 discos se contrastan con fuentes publicadas en las respuestas comprobadas.

Con 5 discos, la solución más corta tiene 31 movimientos, y el disco más pequeño se mueve en cada movimiento impar. Como el número de discos es impar, ese disco va primero a la C y luego sigue siempre el ciclo A, C, B.

Édouard Lucas cuenta en el tomo 3 de Récréations mathématiques una regla que atribuye a su sobrino Raoul Olive, alumno del liceo Charlemagne. Según esa regla, el disco más pequeño gira siempre en el mismo sentido, un movimiento de cada dos. Entre dos movimientos suyos solo cabe una jugada válida que no lo toque. De los otros dos discos superiores, solo el menor puede ir sobre el mayor.

Esa es la solución iterativa: mover el pequeño, hacer la única jugada posible con otro disco y repetir. Con un número par de discos, el pequeño empieza hacia la B, y su ciclo es A, B, C. Para 5 discos, de la varilla A a la C, la solución completa queda así.

Con 7 discos la lista llega a 127 movimientos, y el pequeño sigue el mismo ciclo que con 5. El juego muestra la solución de cualquier torre en «La solución, movimiento a movimiento», con el siguiente movimiento resaltado mientras la sigues. «Imprimir la lista de movimientos» imprime solo esa lista, sin el tablero.

La cifra sale de una relación de recurrencia. Para mover el disco mayor, los n - 1 discos que tiene encima deben apartarse antes a la varilla auxiliar. Después el mayor pasa al destino de un solo movimiento, y los n - 1 vuelven a colocarse encima. Por eso T(n) = 2T(n - 1) + 1, con T(1) = 1.

La inducción matemática completa la prueba. Con un disco basta un movimiento, y 2^1 - 1 = 1. Si n - 1 discos piden 2^(n-1) - 1 movimientos, n discos piden el doble más uno, que es 2^n - 1. Tampoco hay atajo: el disco mayor solo puede moverse cuando todos los demás esperan juntos en la tercera varilla.

Así lo explican la revista Plus, de la Universidad de Cambridge, y el capítulo de recursividad de Robert Sedgewick y Kevin Wayne, en Princeton. La sucesión 1, 3, 7, 15, 31 es la A000225 de la OEIS, la enciclopedia en línea de sucesiones de enteros.

En resumen, una torre de n discos se resuelve como mínimo en 2^n - 1 movimientos. Son 7 con 3 discos, 31 con 5, 255 con los 8 del juego original de Lucas y 1023 con 10. Cada disco añadido la duplica y añade uno, como escribía Lucas, porque obliga a trasladar dos veces la torre anterior. Ese crecimiento por potencias de dos es un caso de complejidad exponencial, y por eso las torres grandes se eternizan. En la solución, el disco k se mueve 2^(n-k) veces. El más pequeño lo hace en todos los movimientos impares y el mayor una sola vez, en el movimiento central. Con 5 discos, el pequeño se mueve 16 veces y el mayor, 1.

Qué disco toca en cada paso también tiene fórmula. Según un comentario de Andreas M. Hinz en la sucesión A001511 de la OEIS, el disco del movimiento m es uno más que el número de ceros en que termina m escrito en binario. Los ocho primeros pasos mueven los discos 1, 2, 1, 3, 1, 2, 1 y 4: es la llamada función regla.

La solución recursiva reduce una torre de n discos a dos torres de n - 1, el mismo problema con un disco menos. El capítulo de recursividad de Princeton usa las torres de Hanói como uno de sus ejemplos. Sin código, el algoritmo recursivo cabe en tres órdenes.

1. Mover los n - 1 discos de arriba de la varilla de origen a la auxiliar, usando la de destino como apoyo.
2. Mover el disco mayor del origen al destino.
3. Mover los n - 1 discos de la auxiliar al destino, ahora con el origen como apoyo.

El caso base es la torre de un solo disco, que se mueve directamente. Los pasos primero y tercero vuelven a aplicar las mismas tres órdenes con un disco menos, hasta llegar a ese caso base. Eso es la recursividad: una función que se llama a sí misma con un problema más pequeño y se detiene en un caso que ya sabe resolver.

La solución recursiva y la iterativa producen exactamente la misma lista de movimientos. La recursiva explica por qué funciona; la iterativa, con el disco pequeño girando sin cambiar nunca de sentido, es más cómoda de seguir a mano.

En la ESO, el Real Decreto 217/2022, que fija las enseñanzas mínimas, no nombra el rompecabezas. Encaja, eso sí, en lo que pide para Matemáticas sobre patrones, pautas y regularidades, y sobre pensamiento computacional.

Con la opción «Una posición aleatoria», cada disco empieza en cualquier varilla y todos los repartos son igual de probables. Hay una excepción: el disco mayor nunca empieza en la varilla de destino. Así siempre tiene que moverse. Con 4 discos hacen falta al menos 8 movimientos y como mucho 15, 12,7 de media.

La posición se reparte solo al pulsar «Repartir una posición aleatoria» y viaja en el enlace, con una forma como ?start=random&pos=ABCA, así que quien lo abre recibe el mismo reparto. El segundo contador pasa a llamarse «Mínimo desde el inicio».

Contando todas las posiciones, incluso aquellas en que el mayor ya está en su sitio, la media baja a dos tercios de 2^n - 1. Con 5 discos son 20,7 movimientos, según un recuento exhaustivo propio de este sitio. Esas 243 posiciones forman un grafo, con una línea por movimiento. La revista Plus y el libro de Andreas M. Hinz, Sandi Klavžar y Ciril Petr muestran que se parece cada vez más al triángulo de Sierpinski al añadir discos.

«Pista» resalta las dos varillas del siguiente movimiento de un camino más corto, desde donde estén los discos. También lo escribe, por ejemplo «Pista: mueve el disco 2 de A a C». «Resolver» termina la partida desde la posición actual. Tarda 0,9 segundos entre movimientos en la velocidad lenta y 0,16 en la rápida, y menos aún en la muy rápida.

Mientras resuelve, «Pausa» lo detiene, «Reanudar» lo pone otra vez en marcha y «Un movimiento» avanza de uno en uno. «Jugar desde aquí» te devuelve los discos para seguir por tu cuenta. Si la partida empezó desde una torre y va siguiendo la lista de la solución, el solucionador continúa esa misma lista.

Al completar la torre, el resultado compara tus movimientos con el mínimo y da el tiempo con décimas, las pistas y los movimientos deshechos. «Copiar el resultado» copia una línea con el enlace, que guarda los discos, las varillas, el inicio, el reparto aleatorio, la velocidad y los números.

Édouard Lucas sacó el rompecabezas en 1883 como «la Tour d'Hanoï, véritable casse-tête annamite». Aparecía a nombre de un supuesto «professeur N. Claus (de Siam), mandarin du collège Li-Sou-Stian», según el Journal des Débats del 27 de diciembre de 1883, que citan R. E. Allardice y A. Y. Fraser.

Según el archivo MacTutor de la Universidad de St Andrews, N. Claus de Siam es un anagrama de Lucas d'Amiens, y Li-Sou-Stian, de Saint Louis, el liceo donde enseñaba Lucas. El juego traía 8 discos de madera ensartados en tres clavos sobre una tablilla, «huit pions en bois», como cuenta Lucas en el tomo 3 de Récréations mathématiques (1893).

La leyenda venía con el juego, en la hoja de 1883. En el gran templo de Benarés, en la India, los sacerdotes brahmanes trasladan una torre de 64 discos de oro puro entre tres agujas de diamante. Mueven un disco cada vez y nunca uno mayor sobre uno menor. Cuando terminen, la torre y los brahmanes caerán, y será el fin del mundo.

Es una historia inventada, la leyenda de Lucas, no una tradición antigua. El propio Lucas escribió que el juego no se trajo de Tonkín, «quoi qu'en dise le prospectus». Según él, juego y leyenda se idearon en el número 56 de la rue Monge, en París. Henri de Parville la volvió a contar poco después en la revista La Nature, según W. W. Rouse Ball.

Lucas hizo también la cuenta del templo: 2^64 - 1 = 18.446.744.073.709.551.615 movimientos, un número de 20 cifras, y más de 5 mil millones de siglos. El mismo Lucas describió el juego de los cuadritos, primero como «le jeu de l'École Polytechnique» en 1883 y después como «La Pipopipette» en 1889.

En psicología, las tareas de torres se usan para estudiar la planificación y la resolución de problemas, y en clínica como medida de las funciones ejecutivas. Marianne Freiberger lo resume en la revista Plus diciendo que con estos juegos se puede ver pensar a la gente.

Tim Shallice describió en 1982 una tarea de planificación, la Torre de Londres. Jeremy R. Sullivan, Cynthia A. Riccio y Candace L. Castillo revisaron en 2009 las tareas de torres como medidas del funcionamiento ejecutivo en adultos. Un estudio de la Universidad Erasmus de Róterdam llama a la Torre de Londres un instrumento muy usado para evaluar la capacidad de planificación.

En España, el manual de ANILLAS, de Hogrefe TEA Ediciones, dedica un apartado titulado «Torre de Hanoi» a la evaluación de las funciones ejecutivas. J. A. Portellano explicó a Infocop en 2009 que la batería ENFEN, para niños de 6 a 12 años, se inspira en «pruebas clásicas». Entre ellas cita «la Torre de Hanoi» y el test de Stroop.

Esta página es un rompecabezas, no una prueba clínica. Los movimientos y el tiempo de una partida no miden la inteligencia, la atención ni ningún trastorno. Las pruebas como ANILLAS o ENFEN las aplican profesionales, con sus propias normas de puntuación.