149. Tower of Hanoi

Why this mechanism works

The largest disk cannot move until the n-1 smaller disks have been moved aside. Transfer them to the spare peg, move the largest disk to its destination, then transfer the smaller stack onto it. Each child call has the same contract with renamed peg roles.

State and boundaries

transfer(count,source,target,spare) appends moves that relocate exactly that legal stack while preserving disk order.

Protocol

1. Return immediately for zero disks.
2. Transfer count-1 disks from source to spare.
3. Append one source-to-target move for the largest disk.
4. Transfer count-1 disks from spare to target.
5. Return the accumulated move list.

Visualization

move n-1: A -> B using C
move largest: A -> C
move n-1: B -> C using A

Python implementation

def hanoi(n):
    moves = []
    def transfer(count, source, target, spare):
        if count == 0:
            return
        transfer(count - 1, source, spare, target)
        moves.append((source, target))
        transfer(count - 1, spare, target, source)
    transfer(n, 'A', 'C', 'B')
    return moves

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 hanoi: moves = []
n=3; moves=[]

L4 transfer: if count == 0:
count=3; source='A'; target='C'; spare='B'; moves=[]

L4 transfer: if count == 0:
count=2; source='A'; target='B'; spare='C'; moves=[]

L4 transfer: if count == 0:
count=1; source='A'; target='C'; spare='B'; moves=[]

L4 transfer: if count == 0:
count=0; source='A'; target='B'; spare='C'; moves=[]

L7 transfer: moves.append((source, target))
count=1; source='A'; target='C'; spare='B'; moves=[('A', 'C')]

L4 transfer: if count == 0:
count=0; source='B'; target='C'; spare='A'; moves=[('A', 'C')]

L6 transfer: transfer(count - 1, source, spare, target)
count=2; source='A'; target='B'; spare='C'; moves=[('A', 'C')]

... 18 intermediate state changes omitted ...

L4 transfer: if count == 0:
count=0; source='B'; target='C'; spare='A'; moves=[('A', 'C'), ('A', 'B'), ('C', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('A', 'C')]

L8 transfer: transfer(count - 1, spare, target, source)
count=2; source='B'; target='C'; spare='A'; moves=[('A', 'C'), ('A', 'B'), ('C', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('A', 'C')]

L8 transfer: transfer(count - 1, spare, target, source)
count=3; source='A'; target='C'; spare='B'; moves=[('A', 'C'), ('A', 'B'), ('C', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('A', 'C')]

L9 hanoi: transfer(n, 'A', 'C', 'B')
n=3; moves=[('A', 'C'), ('A', 'B'), ('C', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('A', 'C')]

L2 hanoi: moves = []
n=1; moves=[]

L4 transfer: if count == 0:
count=1; source='A'; target='C'; spare='B'; moves=[]

L4 transfer: if count == 0:
count=0; source='A'; target='B'; spare='C'; moves=[]

L7 transfer: moves.append((source, target))
count=1; source='A'; target='C'; spare='B'; moves=[('A', 'C')]

L4 transfer: if count == 0:
count=0; source='B'; target='C'; spare='A'; moves=[('A', 'C')]

L9 hanoi: transfer(n, 'A', 'C', 'B')
n=1; moves=[('A', 'C')]

Why the solution is correct

By induction, the first child legally clears the largest disk, which can then move to the destination. The second child legally places the smaller stack on it. Any solution must clear and restore those smaller disks around the largest move, yielding the same 2*T(n-1)+1 lower bound met by this construction.

Time and space

Exactly 2^n-1 moves: O(2^n) time/output space and O(n) call-stack space. Materializing large n is inherently impractical.

Common mistakes

Peg names change roles between child calls. Forgetting to exchange the spare and target roles produces illegal moves.

Reasoning card

Transfer exercise

Write a simulator that rejects illegal moves and verifies the final peg contents for every generated small-n sequence.