Solucionar les Torres de Hanoi en Python

Com ja sabreu, ja fa dies que porto intentant aprendre el llenguatge de programació Python, doncs bé, gràcies a l’esforç, ja començo a recollir els fruits i he fet el meu primer programa més o menys “decent”. Per a molts, el programa els hi semblarà completament inútil o bé el consideraran prescindible, ja que és força fàcil de fer, però a mi m’agrada.

El programa no fa res més enllà de donar la solució a l’antic joc de les Torres de Hanoi, que per qui no sàpiga que és aquest joc, es tracta de una base amb 3 pals clavats i en un dels pals hi ha n discs diferents, el més gros a baix de tot i el més petit a dalt. En definitiva, el joc tracta de moure aquests discs de un en un cap als altres pals, tenint en compte que un disc no pot estar en cap moment a sobre d’un altre disc més petit que ell, i el joc s’acaba quan s’aconsegueix traslladar tots els discs, ordenats de més petit a més gran, a un altre pal que no sigui l’inicial. Com que no m’explico molt bé i una imatge val més que 1000 paraules, en poso una per a que us feu una idea.

Bé, doncs finalment us deixo amb el codi Python que he escrit per a donar solució a aquest joc. Si proveu el codi, no fiqueu més de 12 discs, ja que al ser recursiu, crea un arbre de crides immens i pot ser que hagueu de tancar el programa per avorriment, ja que per solucionar el joc s’han de fer (2^n) – 1 moviments com a mínim, i en el cas de 25 discs, s’han de fer (2²⁵)-1 = 33.554.431 moviments, en canvi el cas de 3 discs es soluciona en (2³)-1 = 7 moviments.

Aprofito per ficar una petita taula amb la relació entre el nombre de discs i el mínim de moviments a executar:

• 3 discs – 7 moviments
• 4 discs – 15 moviments
• 5 discs – 31 moviments
• 6 discs – 63 moviments
• 7 discs – 127 moviments
• 8 discs – 255 moviments
• …
• 12 discs – 4095 moviments

# -*- coding: utf-8 -*-
#!/usr/bin/env python

__author__="decline"

def hanoi(num, origen, desti, temp):
    if(num == 1):
        print "Canvio peça "+ str(num) +" de "+ origen +" a "+ desti
    else:
        hanoi(num - 1, origen, temp, desti)
        print "Canvio peça "+ str(num) +" de "+ origen +" a "+ desti
        hanoi(num - 1, temp, desti, origen)

if __name__ == "__main__":
    print "::SOLUCIÓ A LES TORRES DE HANOI::"
    num = int(raw_input("Insereix el número de peces de la Torre de Hanoi: "))
    hanoi(num, 'A', 'B', 'C')

Per últim, cal dir que si sabeu alguna forma alternativa de crear el programa, només cal que la deixeu als comentaris, que accepto correccions. I si algú té alguna pregunta sobre el codi, que també la deixi als comentaris i ja intentaré solucionar els dubtes.

Fins la pròxima, salut!