Also check out: https://www.hackerearth.com/blog/developers/tower-hanoi-recursion-game-algorithm-explained/

towerOfHanoi.py

# Tower of Hanoi
# setup:
# - 3 towers
# - N disks on tower 1 stacked in increasing size (largest on the bottom)
# goal: move the entire stack to another rod
# rules:
# - Only one disk can be moved at a time
# - Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack
# - No disk may be placed on top of a smaller disk.

# Idea:
# - Given the function towerOfHanoi(disk: int, initial_rod: str, destination_rod: str, middle_rod: str)
#   and all disks being stacked on the initial_rod at the start
#   (meaning the nth disk is at the bottom of the stack and 1 is on top)
# - If the disk number is 1 move it from the initial_rod to the destination_rod
# - Else recursively call the function for the disk below it (n-1)
#   1. to move it (and all the disks below it) to the helper rod,
#   2. now we can move the current disk to the empty destination rod,
#   3. and then we move all the other disks from the helper rod on top of the
#      destination rod again

# -1-       |        -1- |
# A   B   C | A   B   C  |
#     1     |     2      |

#  -1-          |               |               |          _1-  |
# --2--         | --2-- -1-     |     -1- --2-- |         --2-- |
#   A    B    C |   A    B    C | A    B    C   | A    B    C   |
#        1      |        2      |      3        |      4        |

#   -1-              |                     |                     |                     |
#  --2--             |  --2--              |                     |          -1-        |
# ---3---            | ---3---         -1- | ---3--- --2--   -1- | ---3--- --2--       |
#    A      B      C |    A      B      C  |    A      B      C  |    A      B      C  |
#           1        |           2         |           3         |           4         |

#                     |                     |                     |               -1-   |
#        -1-          |                     |              --2--  |              --2--  |
#       --2-- ---3--- | -1-   --2-- ---3--- | -1-         ---3--- |             ---3--- |
#  A      B      C    |  A      B      C    |  A      B      C    |  A      B      C    |
#         5           |         6           |         7           |         7           |

def towerOfHanoi(disk: int, initial_rod: str, middle_rod, destination_rod: str, depth: int):
    if disk == 1:
        print(f"{'=' * depth}=> Move {disk=} from {initial_rod!r} to {destination_rod!r}")
        return
    print(f"{' ' * (depth + 3)}Move all disks that are above {disk=} from {initial_rod!r} to {middle_rod!r}")
    towerOfHanoi(disk-1, initial_rod, destination_rod, middle_rod, depth + 1)
    print(f"{'-' * depth}-> Move {disk=} from {initial_rod!r} to empty {destination_rod!r}")
    print(f"{' ' * (depth + 3)}Move all disks that were above {disk=} and moved to the {middle_rod!r} back to the {destination_rod!r}")
    towerOfHanoi(disk-1, middle_rod, initial_rod, destination_rod, depth + 1)

towerOfHanoi(3, initial_rod='initial', middle_rod='middle', destination_rod='goal', depth=0)