Editor

Python Program for the Tower of Hanoi

Intermediate · Recursion

The Tower of Hanoi is a puzzle with three rods and a stack of disks of different sizes on the first rod, smallest on top. The goal is to move the whole stack to another rod, one disk at a time, without ever putting a bigger disk on a smaller one. With 3 disks it takes 7 moves, and recursion gives a short solution for any number of disks.

Program

tower_of_hanoi.py
def hanoi(n, source, target, spare):
"""Move n disks from source to target and return the number of moves."""
if n == 1:
# Base case: a single disk goes straight to the target
print(f"Move disk 1 from {source} to {target}")
return 1
# Recursive step, in three parts:
# 1. Move the n - 1 smaller disks out of the way, onto the spare rod
moves = hanoi(n - 1, source, spare, target)
# 2. Move the biggest disk to the target
print(f"Move disk {n} from {source} to {target}")
moves += 1
# 3. Move the n - 1 smaller disks from the spare rod on top of it
moves += hanoi(n - 1, spare, target, source)
return moves
disks = 3 # or: disks = int(input("How many disks? "))
total = hanoi(disks, "A", "C", "B")
print("Total moves:", total)
print("The formula 2^n - 1 gives:", 2 ** disks - 1)
Output
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Total moves: 7
The formula 2^n - 1 gives: 7

How it works

  1. The rods are called A, B and C, all the disks start on A, and hanoi() moves n disks from source to target using spare as the extra rod.
  2. The base case is a single disk, which can always go straight to the target in 1 move.
  3. For more disks, the recursive step moves the top n - 1 disks to the spare rod, moves the biggest disk to the target, then moves the n - 1 disks from the spare rod onto it.
  4. Moving n - 1 disks is the same puzzle with one disk fewer, which is why the function can call itself to do it.
  5. The function returns how many moves it made, 7 for 3 disks, which matches the formula 2^n - 1, so every extra disk doubles the work.

Other ways to write it

Showing the rods after each move

Showing the rods after each move
rods = {"A": [3, 2, 1], "B": [], "C": []} # the end of each list is the top
def hanoi(n, source, target, spare):
if n == 0: # base case: nothing to move
return
hanoi(n - 1, source, spare, target)
disk = rods[source].pop()
rods[target].append(disk)
print(f"Disk {disk}: {source} -> {target} ", rods)
hanoi(n - 1, spare, target, source)
print("Start:", rods)
hanoi(3, "A", "C", "B")
print("End: ", rods)
Output
Start: {'A': [3, 2, 1], 'B': [], 'C': []}
Disk 1: A -> C   {'A': [3, 2], 'B': [], 'C': [1]}
Disk 2: A -> B   {'A': [3], 'B': [2], 'C': [1]}
Disk 1: C -> B   {'A': [3], 'B': [2, 1], 'C': []}
Disk 3: A -> C   {'A': [], 'B': [2, 1], 'C': [3]}
Disk 1: B -> A   {'A': [1], 'B': [2], 'C': [3]}
Disk 2: B -> C   {'A': [1], 'B': [], 'C': [3, 2]}
Disk 1: A -> C   {'A': [], 'B': [], 'C': [3, 2, 1]}
End:   {'A': [], 'B': [], 'C': [3, 2, 1]}

Each rod is a list used as a stack, so pop() takes its top disk and append() puts it on another rod, and printing the rods after every move shows that a bigger disk never lands on a smaller one; this version uses 0 disks as its base case.

Moves needed for more disks

Moves needed for more disks
def count_moves(n):
if n == 0:
return 0
# move n - 1 disks, move 1 disk, move n - 1 disks again
return 2 * count_moves(n - 1) + 1
print("Disks Moves")
for n in [1, 2, 3, 4, 5, 10, 20, 64]:
print(f"{n:<8}{count_moves(n):,}")
Output
Disks   Moves
1       1
2       3
3       7
4       15
5       31
10      1,023
20      1,048,575
64      18,446,744,073,709,551,615

The move count follows the same recursion as the puzzle, and the legend of monks moving 64 golden disks would need 18,446,744,073,709,551,615 moves.

Try it yourself

Change disks to 4 and check that the program makes 15 moves.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises