Skip to content
PlayBlog
Logic Puzzle

Tower of Hanoi

Move a stack of disks between three pegs following the rules. A foundational recursive-thinking puzzle. Move all the disks from the left peg to the right peg. You can only move one disk at a time, and you can never place a larger disk on top of a smaller one.

0Moves
7Min
Click a peg to select its top disk, then click another peg to move it there.

The rules

Three pegs stand on a board. A stack of disks of decreasing size sits on the leftmost peg, largest at the bottom. Your goal is to move the entire stack to the rightmost peg. You may move only one disk at a time, and you may never place a larger disk on top of a smaller one.

The mathematics

For N disks, the minimum number of moves required is 2N − 1. So three disks need 7 moves, four need 15, five need 31, and so on. The puzzle was invented by French mathematician Édouard Lucas in 1883, who accompanied it with a (fictional) legend about monks in a temple moving 64 golden disks. At one move per second, 64 disks would take 264 − 1 seconds — about 585 billion years, roughly 42 times the current age of the universe.

Why 2N − 1 is the minimum

The argument is recursive. To move N disks from peg A to peg C, you must:

  1. Move the top N − 1 disks from A to B (using C as auxiliary). This takes at least M(N − 1) moves.
  2. Move the largest disk from A to C. This takes 1 move.
  3. Move the N − 1 disks from B to C (using A as auxiliary). This takes at least M(N − 1) moves.

So M(N) ≥ 2·M(N − 1) + 1, with M(1) = 1. Solving this recurrence gives M(N) = 2N − 1. The lower bound is tight — there's an algorithm that achieves it.

Worked example: 3 disks in 7 moves

Label the pegs A (left), B (middle), C (right). Start: all 3 disks on A.

  1. Move disk 1 (smallest) A → C.
  2. Move disk 2 A → B.
  3. Move disk 1 C → B (on top of disk 2).
  4. Move disk 3 (largest) A → C.
  5. Move disk 1 B → A.
  6. Move disk 2 B → C.
  7. Move disk 1 A → C. Done.

Why this puzzle is taught in computer science

The Tower of Hanoi is the canonical example of recursion in computer science. The solution algorithm calls itself on a smaller subproblem (move N−1 disks), then performs one step, then calls itself again. It's a clean illustration of how a problem that would be tedious to spell out iteratively can be expressed in three lines of recursive code. Solving the puzzle by hand teaches the same insight the algorithm embodies: the largest disk only moves once, and everything else is two recursive calls on smaller stacks.

Strategy tips

  • The largest disk moves exactly once. When you move it, the move must be from the source peg to the destination peg. If you find yourself moving the largest disk more than once, you've gone wrong.
  • Work backward. Before moving the largest disk, you need all other disks stacked on the auxiliary peg. So the sub-goal is: "get disks 1 through N−1 onto the middle peg."
  • The smallest disk moves on every other move. Specifically, on moves 1, 3, 5, 7, … the smallest disk moves. It cycles through the pegs in a fixed direction (clockwise if N is even, counter-clockwise if N is odd).
Related The Tower of Hanoi shares its recursive structure with our Sliding Puzzle — both are state-space search problems where the path to the solution is non-obvious.