La torre de Hanoi
La torre de Hanoi
En una pagoda de Hanoi hay tres varillas. En la primera varilla se ven varios discos de oro de tamaños distintos, cada uno enhebrado sobre otro de mayor diámetro. Un monje, con parsimonia, mueve un disco por vez, quitándolo de donde esté y enhebrándolo en una varilla distinta. Sigue una regla estricta: en ningún caso puede ubicar un disco sobre otro más pequeño. Se dice que la pagoda, las varillas y los discos fueron creados al principio de los tiempos; cuando el monje traslade todos los discos a la última varilla se terminará el mundo.
Podemos estar tranquilos: el fin del mundo no está cerca, porque esa historia es pura fantasía. La torre de Hanoi fue inventada por un matemático francés llamado Edouard Lucas en 1883. Quizás para darle relumbre exótico, se presentó como una creación del profesor N. Claus, de Siam, nombre que bien mirado es un anagrama de Lucas, d'Amiens.
¿Cómo se resuelve? Podés mover discos al tuntún de allá para acá, pero con esa actitud no te admitirían en ninguna pagoda. Hay un sistema eficaz, interesante y muy instructivo que vale la pena conocer.
La idea general es esta. Primero hay que mover todos los discos, excepto el más grande, hasta la varilla auxiliar. Luego hay que mover el disco mayor hasta la última varilla. Finalmente, hay que mover todos los discos de la varilla auxiliar hasta la última varilla.
Supongamos que hay ocho discos. Hay que mover siete hasta la varilla auxiliar. Luego hay que mover el octavo a la última varilla, y después hay que mover los otros siete hasta su ubicación definitiva.
Bien: si supiéramos cómo mover siete discos, ya sabemos cómo mover ocho. Pero, ¿cómo se mueven siete discos?
Es fácil. Con la misma idea. Se mueven seis hasta la varilla auxiliar, luego se mueve el septimo a la posición deseada, y finalmente se mueven los seis anteriores.
Si sabemos cómo mover seis entonces sabemos cómo mover siete, y si sabemos cómo mover siete entonces sabemos cómo mover ocho. ¿Y cómo se mueven seis discos?
Ya te imaginarás cómo sigue. De esta manera vamos reduciendo la complejidad del problema hasta quedarnos con un desafío indudablemente a nuestro alcance: mover un solo disco.
Este truco es conocido como algoritmo recursivo. Te animamos a que lo pruebes por vos mismo en este pequeño ejemplar en Flash. Podés elegir la cantidad inicial de discos. Cuidado: la cantidad de movimientos necesarios para resolverlo crece rápidamente. Con cuatro discos son necesarios quince movimientos. Con ocho discos son necesarios 255 movimientos. Pero con veinte discos ya hacen falta más de un millón de movimientos.
