¿Que son las Torres de Hanoi?

Se conoce como un juego matemático inventado por el francés Édouard Lucas en 1883. Consiste en pasar n discos apilados y ordenados por tamaño de una estaca a otra, garantizando que un disco de radio R nunca se ponga encima de otro de radio r (asumiendo que R>r)

Además solo es posible mover un disco a la vez y siempre el disco en el tope de la pila.


Vamos a realizar su algoritmo en Python usando recursividad.

  • Primero definimos la función tomando como parametros la cantidad de discos y las tres estacas, nombradas como: TorreOrigen, TorreAuxiliar y TorreDestino.
def Hanoi(discos,TorreOrigen=1,TorreAuxiliar=2,TorreDestino=3)

A los valores de las torres les pongo sus nombres por defecto ya que siempre serán las mismas.

  • El Algoritmo será recursivo y el caso base para este problema tiene lugar cuando se cuenta con un solo disco a mover.

Pero..¿que es recursivo y caso base?

Pues vamos a explicarlo.

La recursividad es una de las herramientas más potentes e importantes en Computación. El concepto no se limita solo al ambito de la programación si no que se encuentra presenta en la propia naturaleza donde diferentes organizamos presentan estructuras recursivas. Objetos cuya estructura geométrica ya sea fragmentada o irregular se repite a diferentes escalas.

Una función es recursiva cuando se define en términos de si misma, como por ejemplo.

f(1)=1

f(2)=2

f(n)=f(n-1) + 2* f(n-2)

Para n>0, siendo n un entero

Un ejemplo de recursividad en Python

def suma(numeros):

    if len(numeros) is 0:

       return 0

   return numeros[0] + suma(numeros[1:len(numeros)])

La recursividad se divide en 2 casos:

  • El caso base que define el final de la recursión y representa una entrada del problema para el que se conoce fácilmente la solución

En el ejemplo de la suma, el caso base se alcanza cuando la longitud de la lista de números es cero. Evidentemente la suma de una lista que no contiene números es cero.

  • El caso recursivo donde se define una regla general para resolver el problema reduciendolo a un problema de menor tamaño.

En el caso recursivo, vemos la suma de una lista de números como la suma del primer elemento + la suma de los restantes. Esta formulación es válida y así tambien se llega al resultado final.

Ahora que ya sabemos qué es Recursividad y caso base continuamos con nuestro algoritmo para resolver las Torres de Hanoi.

¿Cuál será nuestro caso base?. Pues cuando solo nos quede un disco por pasar.

if discos ==1:

    print (TorreOrigen,»a»,TorreDestino)

Recursivamente el problema se resuelve notando que al mover cada disco de la TorreOrigen a la TorreDestino, primero deben moverse todos los n-1 discos apilados encima del disco mayor en TorreOrigen hacia la TorreAuxiliar. Luego mover este disco mayor de TorreOrigen a TorreDestino y finalmente los n-1 que fueron apilados en TorreAuxiliar hacia TorreDestino.

De esta forma ya tenemos resuelto nuestro algoritmo para las Torres de Hanoi con n discos.

Pero esto cómo se expresa en código.

else:

    Hanoi(n-1,TorreOrigen,TorreDestino,TorreAuxiliar)

    print (TorreOrigen,»a»,TorreDestino)

    Hanoi(n-1,TorreAuxiliar,TorreOrigen,TorreDestino)

Pues ya está!!!. Vamos a juntar ambas partes y tenemos un programa elegante y muy optimizado para resolver este famoso rompecabezas del año 1883.

Para que os resulte más fácil aquí os dejo el código sobre una consola online para que podáis hacer vuestras pruebas.