Torres de Hanoi

De Wikipedia, la enciclopedia libre

Torres de Hanoi
Torres de Hanoi

Las Torres de Hanoi es un juego matemático. Consiste en tres varillas verticales y un número indeterminado de discos que determinarán la complejidad de la solución. No hay dos discos iguales, están colocados de mayor a menor en la primera varilla ascendentemente, y no se puede colocar ningún disco mayor sobre uno menor a él en ningún momento. El juego consiste en pasar todos los discos a la tercera varilla colocados de mayor a menor ascendentemente.

Tabla de contenidos

[editar] Leyenda

En un templo de Benarés, se encontraba un cúpula que señalaba el centro del mundo. Allí estaba una bandeja sobre la cual existían tres agujas de diamante. En una mañana lluviosa, un rey mandó a poner 64 discos de oro, siendo ordenados por tamaño: el mayor en la base de la bandeja y el menor arriba de todos los discos.

Después de la colocación, los sacerdotes del templo intentaron mover los discos entre las agujas, según las leyes que se les habían entregado: "El sacerdote de turno no debe mover más de un disco a la vez, y no puede situar un disco de mayor diámetro encima de otro de menor diámetro".

Hoy no existe tal templo, pero el juego aún perduró en el tiempo...

Otra leyenda cuenta que Dios al crear el mundo, colocó tres varillas de diamante con 64 discos en la primera. También creó un monasterio con monjes, los cuales tienen la tarea de resolver esta Torre de Hanoi divina. El día que estos monjes consigan terminar el juego, el mundo acabará.

No obstante, este leyenda resultó ser un invento publicitario del creador del juego, un matemático de fortuna del siglo XVIII (¿El matemático frances Edouard Lucas en 1883?). En aquella época, era muy común encontrar matemáticos ganándose la vida de forma itinerante con juegos de su invención, de la misma forma que los juglares hacían con su música. No obstante, la falacia resultó ser tan efectista y tan bonita, que ha perdurado hasta nuestros días. Además, invita a realizarse la pregunta: "si la leyenda fuera cierta, ¿cuándo será el fin del mundo?"

El mínimo número de movimientos que se necesita para resolver este problema es de 264-1. Si los monjes hicieran un movimiento por segundo, los 64 discos estarían en la tercera varilla en poco menos de 585 mil millones de años. Como comparación para ver la magnitud de esta cifra, la Tierra tiene como 5 mil millones de años, y el Universo entre 15 y 20 mil millones de años de antigüedad, sólo una pequeña fracción de esa cifra.

[editar] Resolución

El problema de las Torres de Hanoi es curioso porque su solución es muy rápida de calcular, pero el número de pasos para resolverlo crece exponencialmente conforme aumenta el número de discos.

Existen otras versiones del problema con un número diferente de varillas. Aunque se conocen algoritmos eficientes que resuelven el problema con 3 varillas de manera óptima, no se han encontrado aún sus contrapartidas para cualquier número (N igual o superior a 3) de ellas.

[editar] Mediante recursividad

Este problema se suele plantear a menudo en ámbitos de programación, especialmente para explicar la recursividad. Si numeramos los discos desde 1 hasta n, y llamamos X a la primera pila de discos (origen), Z a la tercera (destino) e Y a la intermedia (auxiliar) y a la función le llamaríamos hanoi(origen,auxiliar,destino), como parametros, la función recibiría las pilas de discos. El algoritmo de la función sería el siguiente:

  1. Si origen == {1}: mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino); terminar.
  2. Si no: hanoi({1...n−1},destino,auxiliar)     //mover todas las fichas menos la más grande (n) a la varilla auxiliar
  3. mover disco n a destino                //mover la ficha grande hasta la varilla final
  4. hanoi(auxiliar,origen,destino)          //mover todas las fichas restantes, {1...n−1}, encima de la ficha grande (n)
  5. terminar
Resolución de la torre de cuatro discos
Resolución de la torre de cuatro discos

[editar] Iterativa

Otra manera de resolver el problema, sin utilizar la recursividad, se basa en el hecho de que para obtener la solución más corta, es necesario mover el disco más pequeño en todos los pasos impares, mientras que en los pasos pares sólo existe un movimiento posible que no lo incluye. El problema se reduce a decidir en cada paso impar a cuál de las dos pilas posibles se desplazará el disco pequeño:


El algoritmo en cuestión depende del número de discos del problema.

  • Si inicialmente se tiene un número impar de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila destino, y en cada paso impar se le mueve a la siguiente pila a su izquierda (o a la pila destino, si está en la pila origen).
La secuencia será DESTINO, AUXILIAR, ORIGEN, DESTINO, AUXILIAR, ORIGEN, etc.
  • Si se tiene inicialmente un número par de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila auxiliar, y en cada paso impar se le mueve a la siguiente pila a su derecha (o a la pila origen, si está en la pila destino).
La secuencia será AUXILIAR, DESTINO, ORIGEN, AUXILIAR, DESTINO, ORIGEN, etc.

[editar] Curiosidades

A la hora de resolver matemáticamente el problema, nos encontramos con muchas curiosidades matemáticas respecto a la resolución. Son las siguientes:

  • La ficha número n (siendo 1 la más pequeña) se mueve por primera vez en el paso número 2^(n-1), y después de ese primer movimiento, se moverá cada 2^n movimientos. De este modo, la ficha 1, se mueve en 1, 3, 5, 7, 9... etc. La ficha 3, se mueve en 4, 12, 20, 28, 32... etc
  • Todas las fichas impares (siendo 1 la más pequeña) se mueven siguiendo el mismo patrón. Asimismo, todas las fichas pares se mueven siguiendo el patron inverso a las impares. Por ejemplo: si queremos mover un numero impar de piezas desde la columna 1 hasta la 3, sucederá lo siguiente:
  • Todas las fichas impares seguirán este patrón de movimiento: 1 -> 3 -> 2 -> 1 -> 3 -> 2 -> 1 -> 3 -> 2 -> 1.
  • Todas las fichas pares seguirán este patrón de movimiento: 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3
Estos patrones dependen únicamente del número de piezas. Si el número de piezas es par, los patrones de las impares serán los de las pares, y viceversa.
  • Uniendo la primera regla con la segunda, sabemos siempre qué pieza hay que mover y a qué columna hay que desplazarla, luego el problema está resuelto.

[editar] Véase también

[editar] Enlaces externos

Herramientas personales