Python program: Tower of Hanoi
Move a stack of discs between three pegs, one disc at a time, never putting a larger disc on a smaller one.
The code
def hanoi(n, source, target, spare, moves): if n == 0: return hanoi(n - 1, source, spare, target, moves) # move the smaller stack out of the way moves.append((n, source, target)) # move the biggest disc hanoi(n - 1, spare, target, source, moves) # put the smaller stack back on top moves = [] hanoi(3, "A", "C", "B", moves) for disc, a, b in moves: print(f"move disc {disc} from {a} to {b}") print(len(moves), "moves (always 2**n - 1)")
Output
move disc 1 from A to C move disc 2 from A to B move disc 1 from C to B move disc 3 from A to C move disc 1 from B to A move disc 2 from B to C move disc 1 from A to C 7 moves (always 2**n - 1)
How it works
The recursive idea: to move n discs, move n−1 out of the way, move the biggest, then move the n−1 back on top. The base case is zero discs.
Python features used
Learn the ideas behind it in the free lesson More Functions.