Editor

Tower of Hanoi in Python

Tower of Hanoi moves a stack of disks from one peg to another, one disk at a time, never putting a bigger disk on a smaller one. Recursion solves it in three lines of thought: move the disks above, move the biggest, move the others back on top.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. To move n disks from source to target, first move the top n - 1 disks to spare, out of the way.
  2. Then move the biggest of the n disks straight from source to target.
  3. Then move the n - 1 disks from spare onto target, on top of it.
  4. Each of those smaller moves is the same puzzle with one disk fewer, so the function calls itself. With 0 disks there is nothing to do.
  5. 3 disks take 7 moves. n disks always take 2ⁿ - 1 moves.

What to watch

  • Watch source, target and spare swap roles from one call to the next.
  • Watch the lists in pegs change by one disk at each move. A bigger number never lands on a smaller one.
  • Watch disk 3 make its only move, from A to C, right in the middle: it is move 4 of 7.

The code

pegs = {"A": [3, 2, 1], "B": [], "C": []}   # disk 3 is the biggest

def hanoi(n, source, target, spare):
    if n == 0:
        return                               # no disks: nothing to do
    hanoi(n - 1, source, spare, target)      # clear the smaller disks away
    disk = pegs[source].pop()
    pegs[target].append(disk)
    print("Move disk", disk, "from", source, "to", target)
    hanoi(n - 1, spare, target, source)      # put them back on top

hanoi(3, "A", "C", "B")
print(pegs)
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
{'A': [], 'B': [], 'C': [3, 2, 1]}

Open it in the editor · Python Program for the Tower of Hanoi, explained