AlgoVerse

Tower of Hanoi

Move n disks from peg A to peg C, one at a time and never a larger disk on a smaller one; exactly 2ⁿ − 1 moves.

To move k disks from the source peg to the goal:

Read the full explanation ↓
Input:
n=3PDF export

Three disks: 7 moves.

  1. def hanoi(n):
  2. pegs = {"A": list(range(n, 0, -1)), "B": [], "C": []}
  3. moves = []
  4. solve(n, "A", "C", "B", pegs, moves)
  5. return moves
  8. def solve(k, src, dst, via, pegs, moves):
  9. if k == 0:
  10. return
  11. solve(k - 1, src, via, dst, pegs, moves)
  12. disk = pegs[src].pop()
  13. pegs[dst].append(disk)
  14. moves.append((disk, src, dst))
  15. solve(k - 1, via, dst, src, pegs, moves)

Invariant: On every peg the disks are always stacked from large (bottom) to small (top).

Start

pegs—

The table is still empty.

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

n3

Orange = changed in this step

Call stack

  1. hanoi()line 1
Step 1 of 78
Black = move · Orange = key stepmove: 0/7
    Explanation

    The idea

    To move k disks from the source peg to the goal:

    1. move the top k − 1 disks (recursively) to the spare peg;
    2. move the largest disk to the goal;
    3. move those k − 1 disks (recursively) from the spare peg on top of it.

    How many moves?

    T(k) = 2·T(k−1) + 1 and T(0) = 0, so T(n) = 2ⁿ − 1. No fewer are possible: the largest disk must move at least once, and before that all the others must be out of the way.

    What to watch in the trace

    • The pegs card shows the three pegs (bottom to top) and the table lists all moves so far.
    • The call tree is a complete binary tree of depth n.
    • Disk 1 moves on every other move.