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 Édouard Lucas.  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:

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.



 

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.

Otra historia indica que fue cosa Divina y que los monjes tienen la tarea de resolver esta Torre de Hanói. El día que estos monjes consigan terminar el juego, el mundo acabará.









 

 

Algoritmo (recursivo) Torres de Hanói ( Complejidad   2^n  )

Entrada: Tres pilas de números origen, auxiliar, destino, con la pila origen ordenada Salida: La pila destino Si origen == { 0 }  entonces mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino) terminar Si no hanoi({0,...,n-1}, destino, auxiliar) //mover todas las fichas menos la más grande (n) a la varilla auxiliar Mover disco n a destino //mover la ficha grande hasta la varilla final hanoi (auxiliar, origen, destino) //mover todas las fichas restantes, 0...n-1, encima de la ficha grande (n) terminar      6. El resultado es: La pila destino Implementación Java



 

 

Resolución 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, y esto lo dejo para que lo descubráis ensayando con el juego, pero hay que probar con distinto número de discos, y lejos de esos 64, jeje, hacedlo con 5, 4 ó 3.

Implementado en código C de forma elegante y bastante críptica, jeje.

#include <stdio.h>

#include <stdlib.h>

int main()

{

    int n, x;

    printf( "Numero de discos? " );

    scanf( "%d", &n ); printf("\n"); 

    for (x=1; x < (1 << n); x++) // 2^n

        printf( "de %i a %i\n",

                 (x&x-1)%3, ((x|x-1)+1)%3 );

    printf("\n una tecla para salir.");

    getch();

    return 0;

}

 

 

¿Aun no es el final?

El único fracaso de verdad es no llegar a intentado, y el éxito
se mide por como afrontamos la decepción, ya que siempre llega.

Vinimos aqui y lo intentamos, todos nosotros, a nuestra manera.

¿A caso no es normal que nos sintamos demasiado viejos para cambirar,
que nos asuste demasiado la decepción para empezar todo de nuevo?

Por la mañana nos levantamos y hacemos todo lo que podemos,
todo lo demás no importa.

Pero también es cierto que la persona que no arriesga nada,
no consigue nada, no tiene nada.
Lo único que sabemos del futuro
es que será distinto.

Pero quizá nuestro temor
es que todo siga siendo igual.
Por eso debemos celebrar los cambios.

Porque como dijo alguien una vez:
"Al final todo saldrá bien,
y si no sale bien,
-hacedme caso,
es que aun no es el final."