TORRES DE HANOI

El segundo ejemplo más usado para la recursividad, es el juego de las Torres de Hanoi.
¿En que consiste el juego?

Representación Gráfica del juego

El juego tiene como elementos un base que contiene tres torres o varillas, en la primera, se encuentra una cierta cantidad de discos de diferentes tamaños ordenados de mayor a menor, de abajo hacia arriba. El juego consiste en llevar todos los discos a la tercera torre usando la segunda como auxiliar, tomando en cuenta las siguientes reglas:

1. Solo se puede mover un disco a las vez, por lo tanto soló se moverá el disco que está arriba de cualquiera de las torres
2. No se puede colocar un disco sobre otro mas pequeño

Este juego está basado en un leyenda muy antigua, aquí la tienen:

La leyenda...

“En el gran templo de Benarés, debajo de la cúpula que marca el centro del mundo, yace una base de bronce, en donde se encuentran acomodadas tres agujas de diamante, cada una del grueso del cuerpo de una abeja y de una altura de 50 cm aproximadamente. En una de estas agujas, Dios, en el momento de la Creación, colocó sesenta y cuatro discos de oro -el mayor sobre la base de bronce, y el resto de menor tamaño conforme se va ascendiendo-. Día y noche, incesantemente, los sacerdotes del templo se turnan en el trabajo de mover los discos de una aguja a otra de acuerdo con las leyes impuestas e inmutables de Brahma, que requieren que siempre haya algún sacerdote trabajando, que no muevan más de un disco a la vez y que deben colocar cada disco en alguna de las agujas de modo que no cubra a un disco de radio menor. Cuando los sesenta y cuatro discos hayan sido transferidos de la aguja en la que Dios los colocó, en el momento de la Creación, a otra aguja, el templo y los brahmanes se convertirán en polvo y, junto con ellos, el mundo desaparecerá...

.... y siguiendo con el tema....

Problema: 

• Realizar un programa que muestre indicaciones para resolver el juego de las Torres de Hanoi, con n discos.

Nota: Usaremos dos clases, Torres De Hanoi y Jugar, en  la primera se harán las operaciones correspondientes y en el segundo se hará uso de la primera clase.

1ra. Clase: Torres.

• Diagrama UML:

• Programa:

package Torres_de_Hanoi;

import javax.swing.JOptionPane;

public class TorresDeHanoi {

    private int NumeroDeDiscos; // Esta variable nos indicará                                        cuantos discos van a usarse.

    private int NumeroDeMovimientos;
// Indicará el total de movimientos hechos para resolver el juego

    public int getNumeroDeDiscos(){//encapsulamiento de variables

        return NumeroDeDiscos;

    }

    public void setNumeroDeDiscos(int NumeroDeDiscos) {

        this.NumeroDeDiscos = NumeroDeDiscos;

    }

    public int getNumeroDeMovimientos() {

        return NumeroDeMovimientos;

    }

    public void setNumeroDeMovimientos(int NumeroDeMovimientos) {

        this.NumeroDeMovimientos = NumeroDeMovimientos;

    }

    public void Captura(){

    NumeroDeDiscos=Integer.parseInt(JOptionPane.showInputDialog("¿CUANTOS DISCOS SON?:"));

    }

    public void Intercambio(int NumDiscos, char A, char B, char C){ 
//Los parámetros se envían a la segunda clase

/*Tomemos en cuenta que el parámetro A, tomará el lugar de la torre inicio, la que inicialmente contiene todos los discos; el parámetro B, será la torre auxiliar; y el parámetro C será la torre destino, donde quedarán al final de juego todas las fichas*/      

       if (NumDiscos==1){
/*si el número de discos es igual a uno, lógicamente se moverá el disco de la torre inicio directamente a la de destino*/ 

           setNumeroDeMovimientos(getNumeroDeMovimientos()+1);

           JOptionPane.showMessageDialog(null, "Mover disco "+NumDiscos+" de la torre "+A+" a la torre "+C+"\nMOVIMIENTOS: "+NumeroDeMovimientos);

           }

        else{/*si la condicion primera no se cumple, quiere decir que se realizarán mas movimientos y serán los siguientes*/

            Intercambio(NumDiscos-1,A,C,B); 
/*... y entonces el método se llama a sí mismo, moviendo primero, el disco de la torre A, inicio, a la torre C, destino*/

            setNumeroDeMovimientos(getNumeroDeMovimientos()+1);
//se suman los movimientos efectuados

            JOptionPane.showMessageDialog(null,"Mover disco "+NumDiscos+" de la torre "+A+" a la torre "+C+"\nMOVIMIENTOS: "+NumeroDeMovimientos);

            Intercambio(NumDiscos-1,B,A,C);
/*... el método vuelve a llamarse a sí mismo, esta vez los parámetros donde de se encontraba la variable A ahora estará la variable B, para indicar el siguiente movimiento*/

           }

    }

    public void Movimientos() {

    JOptionPane.showMessageDialog(null,"TOTAL DE MOVIMIENTOS: "+NumeroDeMovimientos);

    }

}

    

2da. Clase: Jugar.

Nos vamos directamente con el programa...

• Programa

package Torres_de_Hanoi;

import javax.swing.JOptionPane;

public class Jugar {

    public static void main(String arg[]){

     TorresDeHanoi k;

     

     k=new TorresDeHanoi(); 
// se declara y crea la variable que llama a la primera clase  

     k.Captura();                        

     k.Intercambio(k.getNumeroDeDiscos(),'A','B','C'); 
// se reciben los parámetros de el método Intercambio

     k.Movimientos();

    }

}

Ejecutar el programa

Aparte de los objetos corridos por el programa le acompañaré con una representación paso a paso de el juego.

Corremos el programa, desde la clase jugar, y la primera ventana nos pide el numero de discos a usar, en este caso, usaremos tres, y entonces nuestros elementos quedarán así...

y los movimientos serán de la siguiente manera.....

...movimiento #1...

.... movimiento #2...

.... movimiento #3....

.... movimiento #4....

.... movimiento #5....

.... movimiento #6....

.... movimiento #7....

... y finalmente.

Conclusión:

Las torres de Hanoi es uno de los ejemplos usados para el tema de recursividad, debido a que este juego forma parte de los problemas que se resuelven usando este termino. Se podría explicar la recursividad como un procedimiento que se usa cuando se requiere de que cierta acción, se tenga que hacer repetidas veces hasta cumplir con cierto límite, tenemos el ejemplo de las Torres de Hanoi, aquí se tiende a realizar la misma acción, misma que consiste en sacar una ficha de una torre y colocarla en otra, la veces necesarias hasta que todos los discos queden en la torre destino.