TORRES DE HANOI

Las Torres de Hanói es un rompecabezass o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.
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.

Las reglas son:

Sólo se puede mover un disco cada vez.
Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.

RESOLUCION

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 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.

Otra manera de resolverlo es basándose en el disco más pequeño, en este caso el de hasta arriba. El movimiento inicial de este es hacia la varilla auxiliar. El disco número dos por regla, se debe mover a la varilla número tres. Luego el disco uno se mueve a la varilla tres para que quede sobre el disco dos. A continuación se mueve el disco que sigue de la varilla uno, en este caso el disco número tres, y se coloca en la varilla dos. Finalmente el disco número uno regresa de la varilla tres a la uno (sin pasar por la dos) y así sucesivamente. Es decir, el truco está en el disco más pequeño.

1- 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 parámetros, la función recibiría las pilas de discos.

El algoritmo de la función sería el siguiente:

Si origen == {0}: 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

2- Mediante Iteratividad:

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.

****_ ALGORITMO EN JAV@_****

import java.util.Stack;

class Hanoy {

// Las 3 pilas de discos

private Stack columnas[];

// Constructor, toma el nº de fichas total

public Hanoy(int fichas) {

columnas = new Stack[3];

// Inicializamos las columnas vacias

columnas[0] = new Stack();

columnas[1] = new Stack();

columnas[2] = new Stack();

// Colocamos en la primera las fichas, de mayor a menor

for (int i=fichas;i>0;i--) columnas[0].push(i);

}

// Muestra el estado actual

public void Mostrar() {

for (int i=0;i<3;i++)>

System.out.print("Col. "+i+": ");

for(int n : columnas[i]) System.out.print("["+n+"]");

System.out.println("");

}

}

// Mueve de la columna origen a la columna destino 1 disco

public void Mover(int origen, int destino) {

// Mostramos en pantalla lo que hacemos

Mostrar();

System.out.println("Movemos desde ("+origen+") hasta ("+destino+")"); System.out.println("");

// Y luego, lo hacemos, claro

columnas[destino].push(columnas[origen].pop());

}

// Mueve de la columna origen a la columna destino varios discos

public void MoverN(int origen, int destino, int cuantas) {

// Si solo es uno, se mueve sin más

if (cuantas <= 1) Mover(origen,destino);

else {

// Si son varios, entonces:

// - Primero movemos N-1 a la columna ni origen ni destino

MoverN(origen,3 - (origen+destino),cuantas-1);

// - Movemos la N, es decir, la grande

Mover(origen,destino);

// - Movemos las N-1 del primer paso, a la col. destino

MoverN(3 - (origen+destino),destino,cuantas-1);

}

}

// Programa principal

public static void main(String args[]) {

// Creamos una partida de 5 discos

Hanoy h = new Hanoy(5);

// Y la resolvemos (movemos de col.0 a col.2 los 5 discos

h.MoverN(0,2,5);

// Mostramos resultado, resuelto

h.Mostrar();

}

}