Torres de Hanoi

Si pasaste por la lección acerca de recursividad, entonces estás listo para ver otro problema en donde hacer recursividad varias veces realmente ayuda. Se llama las Torres de Hanoi. Te dan un conjunto de tres varillas y $n$‍ discos, con cada disco de un tamaño diferente. Llamemos a las varillas A, B y C, y numeremos los discos desde 1, el disco más pequeño, hasta $n$‍, el disco más grande. Al principio, todos los $n$‍ discos están en la varilla A, en orden de tamaño decreciente de la parte inferior a la parte superior, de modo que el disco $n$‍ está en la parte inferior y el disco 1 está en la parte superior. Aquí está cómo se ven las Torres de Hanoi para $n=5$‍ discos:

El objetivo es pasar todos los $n$‍ discos de la varilla A a la varilla B:

¿Suena fácil, verdad? No es tan sencillo, porque tienes que obedecer dos reglas:

Puedes pensar que este problema no es terriblemente importante. ¡Al contrario! Cuenta la leyenda que en algún lugar de Asia (Tíbet, Vietnam, India; escoge en Internet qué leyenda te gusta), los monjes están resolviendo este problema con un conjunto de 64 discos y, según la historia, los monjes creen que una vez que terminen de mover todos los 64 discos de la varilla A a la varilla B de acuerdo con las dos reglas, el mundo se acabará. ¿Si los monjes están en lo correcto, deberíamos entrar en pánico?

Primero, vamos a ver cómo resolver el problema de manera recursiva. Vamos a empezar con un caso realmente sencillo: un disco, es decir, $n=1$‍. El caso de $n=1$‍ será nuestro caso base. Siempre puedes mover el disco 1 de la varilla A a la varilla B, porque sabes que cualquier disco debajo debe ser mayor. Y no hay nada especial acerca de las varillas A y B. Puedes mover el disco 1 de la varilla B a varilla C si lo deseas, o de la varilla C a la varilla A, o de cualquier varilla a cualquier varilla. Resolver el problema de las Torres de Hanoi con un disco es trivial, y requiere mover el único un disco solamente una vez.

¿Qué pasa con dos discos? ¿Cómo resuelves el problema cuando $n=2$‍? Puedes hacerlo en tres pasos. Aquí está cómo se ve al principio:

Primero, mueve el disco 1 de la varilla A a la varilla C:

Observa que usamos la varilla C como una varilla libre, un lugar en donde poner el disco 1 para que podamos llegar al disco 2. Ahora que el disco 2 (el disco inferior) está expuesto, muévelo a la varilla B:

Por último, mueve el disco 1 de la varilla C a la varilla B:

Esta solución toma tres pasos, y una vez más no hay nada especial acerca de cómo mover los dos discos de la varilla A a la varilla B. Puedes moverlos de la varilla B a la varilla C al usar la varilla A como la varilla libre: mueve el disco 1 de la varilla B a la varilla A, luego mueve el disco 2 de la varilla B a la varilla C y termina por mover el disco 1 de la varilla A a la varilla C. ¿Estás de acuerdo que puedes mover los discos 1 y 2 de cualquier varilla a cualquier varilla en tres pasos? (Di que "sí").

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.