Resolver Las Torres de Hanoi recursivo

Hace algún tiempo se me planteó este típico ejercicio de programación en clase, el llamado Las Torres de Hanoi el cual conseguí resolver después de echarle mucho tiempo y hojas llenas de garabatos. Personalmente fue todo un reto y hoy os mostraré este ejercicio el cual si comprendes completamente, se te abrirá un mundo de posibilidades con la recursividad.

Las Torres de Hanoi

Como explicación muy básica, la recursividad se podría definir como la resolución de un problema de tamaño ( n ), el cual se puede dividir en partes más pequeñas ( <n ) del mismo problema, de los cuales si se conoce la solución.

El juego de Las Torres de Hanoi consiste en mover unos discos desde una varilla vertical a otra, empezando todos los discos en una varilla ordenados de más grande a más pequeño y habiendo 2 varillas más inicialmente vacías. Todo esto siguiendo las siguientes reglas:
  1. Sólo puedes mover los discos de uno en uno.
  2. Los discos tienen que estar ordenados en todo momento, los discos más grandes siempre debajo.
  3. Sólo se puede mover los los discos de arriba de cada barilla.
Teniendo todo esto claro, se puede ver claramente que mover n discos de la varilla origen a la varilla destino, usando una varilla auxiliar, consiste en:
  1. Mover todos los discos menos uno de origen a auxiliar.
  2. Mover el último de origen a destino.
  3. Mover todos los discos menos uno de auxiliar a origen.
  4. Mover el último de auxiliar a destino.
Y este proceso se repite hasta que todos los discos estén en la varilla destino, puedes seguir este proceso en papel para ver como se resuelve el juego con 1, 2, 3, ..., n discos.


Teniendo todo este proceso pasamos a ver el ejercicio resuelto en Javascript, este lenguaje es estupendo para mostrar algoritmos ya que es un lenguaje muy sencillo y se puede seguir claramente sin tener grandes nociones del lenguaje.
var tower1 = [], tower2 = [], tower3 = [];
var n = 5; // Numero de discos

// Coloca en orden n discos en tower1
initTowers();
show(); // Estado inicial de las torres
hanoi(n, tower1, tower2, tower3);
show(); // Estado final de las torres

function hanoi(n, ori, aux, des) {
 // El caso base es mover 1 disco de ori a des
 if(n === 1) 
  mov(ori, des);
 else {
  // Se mueven n-1 discos de ori a aux
  hanoi(n - 1, ori, des, aux);
  mov(ori, des);
  // Se mueven n-1 discos de aux a des
  hanoi(n - 1, aux, ori, des);
 }
}
// Se mueve un disco de la torre ori a des
function mov(ori, des) { 
 des.push(ori.pop()); 
}
function initTowers() {
 for(var i = 0; i < n; i++) 
  tower1.push(n - i);
}
function show() {
 console.log(tower1);
 console.log(tower2);
 console.log(tower3);
 console.log();
}

Comentarios

  1. muchas gracias por la info me a sido muy util!

    ResponderEliminar
  2. Me hubiera gustado que explicaras cómo se sigue el proceso de recursión dentro de la pila interna del lenguaje de programación

    ResponderEliminar

Publicar un comentario

Si tenéis alguna duda o sugerencia, no dudéis en comentar. ;)

Entradas populares de este blog

Ordenar cualquier array con SORT en JAVA

Modificadores de acceso (public, protected y private) JAVA

Calcular factorial de un numero en JAVA