Torres de Hanoi

"Al crear el mundo, Dios situó sobre la Tierra tres varillas de diamante y 64 discos de oro. Los discos son todos de diferente tamaño e inicialmente fueron colocados en orden decreciente de diámetros sobre la primera de las varillas. También creó Dios un monasterio cuyos monjes tienen la tarea de trasladar todos los discos desde la primera varilla a la tercera. La única operación permitida es mover un disco de una varilla a otra cualquiera, pero con la condición de que no se puede situar encima de un disco otro de diámetro mayor. La leyenda dice también que cuando los monjes terminen su tarea, el mundo se acabará".

El otro día alguien preguntó para qué servían los números de Mersenne. El número mínimo de movimientos para resolver el juego de las Torres de Hanoi viene dado por los números de Mersenne (M=2ⁿ-1 con n primo), siendo el n el número de discos a trasladar. Por lo tanto, los monjes hubiesen necesitado 2⁶⁴-1 = 18446744073709551615 movimientos para resolver el juego con 64 discos. Si suponemos que los monjes realizan un movimiento por segundo tardarían 58454204609 siglos y 6 años en completar el traslado, contando con que no descansen ni un solo segundo en ese tiempo ni que cometan ningún fallo, pues el tiempo que hemos calculado ha sido el mínimo número de movimientos, es decir, hemos excluido los posibles fallos. Lógicamente si resolvemos este problema para 64 discos el mundo no se acaba ;) Existe un algoritmo recursivo donde podemos ver una sencilla solución al problema:

hanoi(n, Orig, Aux, Dst)
si (N>0) hacer
hanoi(n-1, Orig, Dst, Aux)
escribir(Movemos Orig a Dst)
hanoi(n-1, Aux, Orig, Dst)

Una posible implementación en Java del algoritmo es la siguiente:

public class TorresDeHanoi {

public static void main(String[] args) {
    TorresDeHanoi tdh = new TorresDeHanoi();
    tdh.hanoi(3, "A", "B", "C"); //Modifica el primer argumento
 }

private void hanoi(int n, String ini, String aux, String fin) {
 if (n > 0) {
  hanoi(n-1,"A","C","B");
  System.out.println("Mover " + n + " de " + ini + " a " + fin);
  hanoi(n-1,"B","C","A");
 }
 }
}

Esta aplicación imprime en pantalla los movimientos mínimos que hay que realizar para resolver el juego para el número de discos que definimos en la instancia del método hanoi (el primer argumento). Probad la clase y podréis ver el algoritmo recursivo en funcionamiento ;)

Más información | Descartes 3D Más información | Torres de Hanoi en Wikipedia