Torres de Hanoi en Java

La leyenda.
En una antigua ciudad en la India, los monjes en un templo tienen que mover una pila de 64 discos sagrados de un lugar a otro.
Los discos son frágiles; sólo pueden ser cargados de uno en uno.
Un disco no debe nunca ser colocado arriba de otro más pequeño.
Además, solamente hay un lugar en el templo (aparte del lugar original y el lugar destino) suficientemente sagrado para poner una pila de discos allí y servir así de apoyo en el traslado de discos desde el origen hasta el destino.
Así que los monjes empiezan moviendo discos atrás y adelante, entre la pila original, la pila en el nuevo lugar de destino, y el lugar intermedio, siempre dejando las pilas en orden(el mayor en la base, el menor en la cima).
La leyenda dice además, que antes de que los monjes realicen el último movimiento para completar la torre en su nuevo lugar, el templo se reducirá a cenizas y el mundo se acabará.
Quizás esta leyenda tenga razón debido a la enorme cantidad de movimientos necesarios para cambiar de lugar los 64 discos
(2^64-1 = 18,446,744,073,709,551,615 movimientos).

Torres de Hanoi
 
Es un juego oriental que consta de tres columnas llamadas origen, destino y auxiliar y una serie de discos de distintos tamaños. Los discos están colocados de mayor a menor tamaño en la columna origen. El juego consiste en pasar todos los discos a la columna destino y dejarlos como estaban de mayor a menor. (el más grande en la base, el más pequeño arriba)
Las reglas del juego son las siguientes:
·         Sólo se puede mover un disco cada vez.
·         Para cambiar los discos de lugar se pueden usar las tres columnas.
·         Nunca deberá quedar un disco grande sobre un disco pequeño.
El problema de las torres de Hanoi se puede resolver de forma muy sencilla usando la recursividad y la técnica divide y vencerás. Para ello basta con observar que si sólo hay un disco (caso base), entonces se lleva directamente de la varilla origen a la varilla destino. Si hay que llevar n>1 (caso general) discos desde origen a destino entonces:

Se llevan n-1 discos de la varilla origen a la auxiliar.
Se lleva un solo disco (el que queda) de la varilla origen a la destino
Se traen los n-1 discos de la varilla auxiliar a la destino.

Utilizando recursividad se obtiene una solución muy simple pero que sorprendentemente funciona:

import java.util.*;
public class Hanoi {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n;
        System.out.println("Numero de discos: ");
        n = sc.nextInt();
        Hanoi(n,1,2,3);  //1:origen  2:auxiliar 3:destino
    }


//Método Torres de Hanoi Recursivo
public static void Hanoi(int n, int origen,  int auxiliar, int destino){
  if(n==1)
  System.out.println("mover disco de " + origen + " a " + destino);
  else{
     Hanoi(n-1, origen, destino, auxiliar);
     System.out.println("mover disco de "+ origen + " a " + destino);
     Hanoi(n-1, auxiliar, origen, destino);
   }
 }
}

Ejercicio
Ejecuta el método anterior para distinto número de discos.
Escribe un método recursivo que calcule el número de movimientos necesarios para mover n discos.

15 comentarios:

  1. Simplemente... excelente explicación!!!

    ResponderEliminar
  2. Perdón en donde inicia la recursividad ?

    ResponderEliminar
    Respuestas
    1. Hanoi(n-1, origen, destino, auxiliar);

      Eliminar
    2. se supone que recursividad es cuando se llama al mismo método hasta que cumpla una condición, y eso no es recursividad.

      Eliminar
    3. Hanoi(n-1, origen, destino, auxiliar); está llamando al propio método con un valor cada vez más pequeño de n hasta que n == 1

      Eliminar
  3. Disculpa, ¿Sabes como hacer para mostrar un determinado movimiento en este ejercicio?
    Por ejemplo así aparecen todos los movimientos necesarios, pero si solo quiero que me aparezca en pantalla el 5to. movimiento????

    Un saludo y gracias de antemano por tu respuesta.

    ResponderEliminar
    Respuestas
    1. Hola JINL,
      Una forma de hacerlo sin modificar el número de parámetros del método Hanoi sería utilizar dos variables de clase. Una como contador de movimientos y otra para el número de movimiento a mostrar. El contador de movimientos se va incrementando con cada movimiento y cuando llegue al valor deseado se muestra el mensaje. No pongo el código para que lo intentes hacer. Dime si lo has conseguido.
      Un saludo y gracias por seguir el blog

      Eliminar
  4. import java.util.Scanner;
    public class DiscosHanoi {
    static int cont=1;
    public static void Hanoi(int n,int origen,int auxiliar,int destino){

    if(n==1){
    System.out.println("Mover de "+origen+" a "+destino);
    }
    else{
    Hanoi(n-1, origen, destino, auxiliar);
    System.out.println("Mover de "+origen+" a "+destino);
    Hanoi(n-1,auxiliar, origen, destino);
    }
    //Primer Contador de movimientos
    cont++;
    }

    public static void contar(int n){
    //Segundo contador de movimientos
    int c=0;
    c=(int)Math.pow(2, n);
    c=c-1;
    System.out.println(cont-1+" - "+"Cantidad de movimientos - "+c);
    }

    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Ingrese numero de discos");
    int n = sc.nextInt();
    Hanoi(n, 1, 2, 3);
    contar(n);
    }
    }

    ResponderEliminar
  5. necesito un código en java que cuando ejecute pueda hacer los movimientos de las torres de hanoi

    ResponderEliminar
  6. alguien sabe por que no funciona la clase Stack y también el push me sale error ??

    ResponderEliminar