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);
        }
    }
}

Ejercicios

1. Ejecuta el método anterior para distinto número de discos.

 

2. Se trata de realizar una modificación del método Torres de Hanoi. Escribe un método recursivo que calcule el número de movimientos necesarios para mover n discos de la torre origen a la torre destino.