Risolvi il problema della Torre di Hanoi in Python

Il problema della Torre di Hanoi è un puzzle matematico fondamentale che viene presentato ai nuovi programmatori all’inizio per ampliare il loro quiz di risoluzione dei problemi.

Il problema è semplice, coinvolge tre canne. Un’asta contiene diversi dischi in ordine decrescente, con il disco più grande in basso e il più piccolo in alto. Dobbiamo trasferire questo dall’asta uno all’asta tre usando la seconda asta.

Dobbiamo tenere a mente alcune regole. Possiamo spostare solo un disco contemporaneamente e dobbiamo prendere il disco nella parte superiore dell’asta. Inoltre, non possiamo posizionare un disco più grande sopra un disco più piccolo.
Tenendo presente tutto questo, dobbiamo risolvere questo problema e calcolare il numero totale di mosse necessarie per risolverlo.

In questo tutorial, introdurremo come risolvere questo problema. Useremo un metodo ricorsivo per risolvere il problema della Torre di Hanoi in Python.

Questo metodo creerà una funzione che si chiamerà ricorsivamente in base ad alcune condizioni per risolvere il problema della Torre di Hanoi.
Implementiamo la logica per questo nel codice seguente.

def ToH(n, A, B, C):
    if n == 1:
        print("Disk 1 from", A, "to", B)
        return
    ToH(n - 1, A, C, B)
    print("Disk", n, "from", A, "to", B)
    ToH(n - 1, C, B, A)


ToH(3, "A", "B", "C")

Produzione:

Disk 1 from A to B
Disk 2 from A to C
Disk 1 from B to C
Disk 3 from A to B
Disk 1 from C to A
Disk 2 from C to B
Disk 1 from A to B

Nell’esempio sopra, spostiamo tre dischi da Rod A a Rod B usando Rod C.

Come puoi vedere, il numero totale di mosse eseguite nell’esempio precedente è 7. Per n numero di dischi, le mosse totali eseguite con questo metodo sono sempre uguali a 2^n -1.

Nel corso del tempo, sono emerse alcune altre soluzioni per risolvere il problema della Torre di Hanoi utilizzando gli stack. Tuttavia, non è consigliabile utilizzarli perché tali metodi sono molto inefficienti in termini di tempo e velocità.