Torres De Hanoi

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

Nos basamos en que sabemos resolver un problema de menor complejidad para resolver uno de mayor complejidad

Mover N discos de origen a destino

• Mover (N-1) discos de origen a auxiliar

• Mover 1 disco origen a destino

• Mover (N-1) disco de auxiliar a destino 

El diagrama de Flujo del algoritmo que vamos a llamar Hanoi(N,origen,destino)

El pseudocódigo de este algoritmo es el siguiente

Hanoi (N, origen,destino)

Si N >1

Auxiliar ← TorreLibre(origen,destino)

Hanoi (N-1,origen,auxiliar)

Print “mover 1 disco de origen a destino

Hanoi(N-1,auxiliar,destino)

En caso contrario

Print “mover 1 disco de origen a destino”

Para calcular la torre auxiliar, dadas un origen y destino cualquiera sabemos que tenemos las siguientes posibilidades:

TORRES DE HANOI

ORIGEN DESTINO AUXILIAR

A B C

A C B

B A C

B C A

C A B

C B A

El diagrama de flujo para calcular la TorreLibre(origen,destino) es el siguiente:

Lo implementamos en Java con la aplicación eclipse:

package hanoi;

/**Programa para resolver el problema de las torres de Hanoi

* @author Nessy */

public class Hanoi {

/**Este método permite determinar qué torre se puede utilizar como auxiliar

* para los movimientos intermedios dadas unas torres de orígen y destino

* cualquiera

* @param origen Torre de origen de los discos.

* @param destino Torre de destino de los discos

* @param auxiliar Torre auxiliar de los discos

*/

static public char torreDisponible(char origen,char destino){

char auxiliar;

if((origen !='A')&& (destino!='A')){

auxiliar='A';

}else if ((origen !='B')&& (destino!='B')){

auxiliar='B';

}else{

auxiliar='C';

}

return auxiliar;

}

/**Resolución del problema de las Torres de Hanoi para el caso de tener n discos y unas torres de origen y destino arbitrarias

* @param n Número de discos a mover.

* @param origen Torre donde están inicialmente los discos

* @param destino Torre a la que mover los discos*/

static public void resolverHanoi(int n,char origen,char destino){

/**n es el número de discos a resolver*/

if(n>1){

char auxiliar =torreDisponible(origen,destino);

resolverHanoi((n-1),origen,auxiliar);

System.out.println("Mover disco de " + origen + " a "+ destino);

resolverHanoi((n-1),auxiliar,destino);

}else{

System.out.println("Mover disco de " + origen + " a "+ destino);

}

}

public static void main(String[] args) {

...