TORRES DE HANÓI

Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.1 Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.

Contenido

[ocultar]

• 1 Descripción

• 2 Historia

• 3 Resolución

• 4 Solución simple

o 4.1 Mediante recursividad

o 4.2 Iterativa

o 4.3 Curiosidades

• 5 Referencias

• 6 Véase también

• 7 Enlaces externos

[editar] Descripción

El juego, en su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:

1. Sólo se puede mover un disco cada vez.

2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.

3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.

Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas.

[editar] Historia

Se cuenta que un templo de Benarés (Uttar Pradesh, India), se encontraba una 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.Tras 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 Hanói divina. El día que estos monjes consigan terminar el juego, el mundo acabará. No obstante, esta leyenda resultó ser un invento publicitario del creador del juego, el matemático Éduard Lucas. 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 son 8 y se debe buscar la diferencia 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 algo 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 Hanói es curiosísimo 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 algunas 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] Solución simple

Una forma de resolver la colocación de la torre es fundamentándose en el disco más pequeño, en este caso el de hasta arriba. El movimiento inicial de este

...