Python Program for Tower of Hanoi Puzzle Solution

Use a recursive Python function like def tower_of_hanoi(n, source, target, auxiliary): to move disks between rods following the rules, printing each move.

Examples

Inputn = 1

OutputMove disk 1 from source to target

Inputn = 3

OutputMove disk 1 from source to target Move disk 2 from source to auxiliary Move disk 1 from target to auxiliary Move disk 3 from source to target Move disk 1 from auxiliary to source Move disk 2 from auxiliary to target Move disk 1 from source to target

Inputn = 0

Output

How to Think About It

Think of the Tower of Hanoi as moving disks from one rod to another using a helper rod. Move the top n-1 disks to the helper rod, then move the largest disk to the target rod, and finally move the n-1 disks from the helper rod to the target rod. Use recursion to repeat these steps until no disks remain.

Algorithm

1

If there are no disks to move, return.

2

Move n-1 disks from source to auxiliary rod using target as helper.

3

Move the nth disk from source to target rod.

4

Move the n-1 disks from auxiliary to target rod using source as helper.

Code

python

def tower_of_hanoi(n, source, target, auxiliary):
    if n == 0:
        return
    tower_of_hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    tower_of_hanoi(n - 1, auxiliary, target, source)

# Example usage:
tower_of_hanoi(3, 'source', 'target', 'auxiliary')

Output

Move disk 1 from source to target
Move disk 2 from source to auxiliary
Move disk 1 from target to auxiliary
Move disk 3 from source to target
Move disk 1 from auxiliary to source
Move disk 2 from auxiliary to target
Move disk 1 from source to target

Dry Run

Let's trace the function with n=2 disks moving from source to target using auxiliary.

1

Call tower_of_hanoi(2, source, target, auxiliary)

n=2, source='source', target='target', auxiliary='auxiliary'

2

Move n-1=1 disk from source to auxiliary

Call tower_of_hanoi(1, source, auxiliary, target)

3

Move disk 1 from source to auxiliary

Print: Move disk 1 from source to auxiliary

4

Move disk 2 from source to target

Print: Move disk 2 from source to target

5

Move n-1=1 disk from auxiliary to target

Call tower_of_hanoi(1, auxiliary, target, source)

6

Move disk 1 from auxiliary to target

Print: Move disk 1 from auxiliary to target

Call	Action
tower_of_hanoi(2, source, target, auxiliary)	Move 1 disk from source to auxiliary
tower_of_hanoi(1, source, auxiliary, target)	Move disk 1 from source to auxiliary
Print	Move disk 1 from source to auxiliary
Print	Move disk 2 from source to target
tower_of_hanoi(1, auxiliary, target, source)	Move disk 1 from auxiliary to target
Print	Move disk 1 from auxiliary to target

Why This Works

Step 1: Recursive Breakdown

The problem is broken down into smaller problems by moving n-1 disks first, which simplifies the task.

Step 2: Base Case

When n is zero, no moves are needed, so the function returns immediately to stop recursion.

Step 3: Moving the Largest Disk

After moving the smaller disks, the largest disk is moved directly to the target rod.

Step 4: Completing the Move

Finally, the smaller disks are moved from the auxiliary rod to the target rod, completing the puzzle.

Alternative Approaches

Iterative approach using stacks

python

def tower_of_hanoi_iterative(n):
    total_moves = 2 ** n - 1
    rods = {'A': list(range(n, 0, -1)), 'B': [], 'C': []}
    if n % 2 == 0:
        target, auxiliary = 'B', 'C'
    else:
        target, auxiliary = 'C', 'B'

    def move_disk(from_rod, to_rod):
        disk = rods[from_rod].pop()
        rods[to_rod].append(disk)
        print(f"Move disk {disk} from {from_rod} to {to_rod}")

    def move_disk_between(rods, rod1, rod2):
        if not rods[rod1]:
            move_disk(rod2, rod1)
        elif not rods[rod2]:
            move_disk(rod1, rod2)
        elif rods[rod1][-1] > rods[rod2][-1]:
            move_disk(rod2, rod1)
        else:
            move_disk(rod1, rod2)

    for i in range(1, total_moves + 1):
        if i % 3 == 1:
            move_disk_between(rods, 'A', target)
        elif i % 3 == 2:
            move_disk_between(rods, 'A', auxiliary)
        else:
            move_disk_between(rods, auxiliary, target)

This method uses loops and stacks but is more complex and less intuitive than recursion.

Using memoization to store moves

python

def tower_of_hanoi_memo(n, source, target, auxiliary, moves=None):
    if moves is None:
        moves = []
    if n == 0:
        return moves
    tower_of_hanoi_memo(n - 1, source, auxiliary, target, moves)
    moves.append((n, source, target))
    tower_of_hanoi_memo(n - 1, auxiliary, target, source, moves)
    return moves

moves = tower_of_hanoi_memo(3, 'source', 'target', 'auxiliary')
for disk, src, tgt in moves:
    print(f"Move disk {disk} from {src} to {tgt}")

Stores all moves in a list before printing, useful for further processing but uses more memory.

Complexity: O(2^n) time, O(n) space

Time Complexity

The function makes two recursive calls for n-1 disks plus one move, resulting in 2^n - 1 moves, so time grows exponentially.

Space Complexity

The recursion stack depth is n, so space complexity is O(n) due to call stack usage.

Which Approach is Fastest?

The recursive approach is simplest and efficient for small n; iterative methods avoid recursion but are more complex to implement.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Simplicity and clarity
Iterative with stacks	O(2^n)	O(n)	Avoiding recursion
Memoization	O(2^n)	O(n + 2^n)	Storing moves for later use