Torres de Hanoi

Torres de Hanoi

¿Que son?

El juego matemático de las Torres de Hanoi consiste en un dispositivo que consta de tres varillas verticales A, B y C y un número variable de discos. Los n discos son todos de diferente tamaño y, en la posición de partida del juego, todos los discos están colocados en la varilla A ordenados de mayor a menor tamaño, esto es, el mayor en el lugar más bajo y el menor arriba. En el mundo de la informática se emplea como el ejemplo de recursividad por excelencia.

Del número de discos depende la complejidad de la solución. El juego consiste en lo siguiente: Comenzando en la posición de partida. Trasladar todos los discos a la varilla B, pero colocados también de mayor a menor, en el mismo orden en el que estaban colocados en la varilla A. Para el traslado de discos podemos utilizar la varilla C, pero se debe cumplir siempre la condición de que sólo se puede mover un disco cada vez y que en ningún caso y en ningún paso se podrá colocar un disco mayor sobre otro de menor radio que él.

¿Como se resuelve?

a solución del problema de las Torres de Hanói es muy fácil de hallar, aunque el número de pasos para resolver el problema crece exponencialmente conforme aumenta el número de discos.Como ya se ha indicado, el número mínimo de movimientos necesarios para resolver un rompecabezas de la Torre de Hanoi es 2ⁿ - 1, donde n es la cantidad de discos.

Una manera sencilla para saber si es posible terminar el "juego" es que si la cantidad de discos es impar la pieza inicial ira a destino y si es par a auxiliar.

Solución simple

Una forma de resolver el problema se fundamenta en el disco más pequeño, el de más arriba en la varilla de origen. En un juego con un número par de discos, el movimiento inicial de la varilla origen es hacia la varilla auxiliar. El disco 2.^o n-1 se debe mover, por regla, a la varilla destino. Luego, el disco n.^o 1 se mueve también a la varilla destino para que quede sobre el disco n.^o 2. A continuación, se mueve el disco que sigue de la varilla origen, en este caso el disco n.^o 3, y se coloca en la varilla auxiliar. Finalmente, el disco n.^o 1 regresa de la varilla destino a la origen (sin pasar por la auxiliar), y así sucesivamente. Es decir, el truco está en el disco más pequeño.

Mediante recursividad

Este problema se suele plantear a menudo en programación, especialmente para explicar la recursividad. Si numeramos los discos desde 1 hasta n, si llamamos origen a la primera pila de discos, destino a la tercera y auxiliar a la intermedia, y si a la función la denomináramos hanoi, con origen, auxiliar y destino como parámetros, el algoritmo de la función sería el siguiente:

Algoritmo Torres de Hanói (Complejidad ${\displaystyle \Theta (2n-1)}$)

Entrada: Tres pilas de números origen, auxiliar, destino, con la pila origen ordenada Salida: La pila destino sí origen ${\displaystyle \scriptstyle ==\{1\}}$ entonces mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino) terminar si no hanoi(${\displaystyle \scriptstyle \{1,\dots ,n-1\}}$,origen,destino, auxiliar)     //mover todas las fichas menos la más grande (n) a la varilla auxiliar mover disco n a destino                //mover la ficha grande hasta la varilla final hanoi (auxiliar, origen, destino)          //mover todas las fichas restantes, 1...n–1, encima de la ficha grande (n) terminar

El número de movimientos mínimo a realizar para resolver el problema de este modo es de 2ⁿ – 1, siendo n el número de discos.