Resolva o problema da Torre de Hanói em Python

O problema da Torre de Hanói é um quebra-cabeça matemático fundamental que é apresentado a novos programadores no início para que eles ampliem seu questionário de resolução de problemas.

O problema é simples, envolvendo três hastes. Uma haste contém vários discos em ordem decrescente, com o maior disco na parte inferior e o menor no topo. Temos que transferir isso da haste um para a haste três usando a segunda haste.

Temos que manter certas regras em mente. Podemos mover apenas um disco simultaneamente e temos que pegar o disco no topo da haste. Além disso, não podemos colocar um disco maior em cima de um disco menor.
Tendo tudo isso em mente, temos que resolver este problema e calcular o número total de movimentos realizados para resolvê-lo.

Neste tutorial, apresentaremos como resolver esse problema. Usaremos um método recursivo para resolver o problema da Torre de Hanoi em Python.

Este método criará uma função que se chamará recursivamente com base em algumas condições para resolver o problema da Torre de Hanói.
Implementamos a lógica para isso no código a seguir.

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")

Resultado:

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

No exemplo acima, movemos três discos da Haste A para a Haste B usando a Haste C.

Como você pode ver, o número total de movimentos feitos no exemplo acima é 7. Para n número de discos, o total de movimentos feitos usando este método é sempre igual a 2 ^ n -1.

Com o tempo, algumas outras soluções surgiram para resolver o problema da Torre de Hanói usando pilhas. Ainda assim, não é recomendado usá-los porque tais métodos são muito ineficientes no tempo gasto e na velocidade.