How to solve the Tower of Hanoi

What is the Tower of Hanoi?

The Tower of Hanoi is a puzzle invented by the French mathematician Edouard Lucas in 1883. You start with three pegs and a stack of disks arranged by size on the leftmost peg, largest at the bottom. The goal is to move the entire stack to the rightmost peg.

Two constraints apply: you can only move one disk at a time (always the top disk from a peg), and you can never place a larger disk on top of a smaller one. These two rules interact to produce a puzzle that is easy to state but surprisingly layered once the disk count goes up.

The rules

1. One disk at a time. You pick up the top disk from any peg and place it on top of another peg. You cannot move a disk that has other disks on top of it.
2. No larger on smaller. A disk can only be placed on an empty peg or on top of a disk that is strictly larger. If the top disk on the destination peg is smaller than the disk you are holding, that move is illegal.
3. All disks to the target peg. The puzzle is solved when every disk sits on the rightmost peg in the original size order (largest at bottom, smallest on top).

Solving 3 disks step by step

Label the pegs A (source), B (auxiliary), and C (target). The disks are numbered 1 (smallest) through 3 (largest). All three start on peg A.

1. Move disk 1 from A to C. Smallest disk goes straight to the target.
2. Move disk 2 from A to B. Middle disk goes to the spare peg.
3. Move disk 1 from C to B. Stack the smallest on top of the middle disk.
4. Move disk 3 from A to C. The largest disk moves directly to the target.
5. Move disk 1 from B to A. Get the smallest disk out of the way.
6. Move disk 2 from B to C. Middle disk joins the largest on the target peg.
7. Move disk 1 from A to C. Done. All three disks on peg C.

Seven moves, and that is the minimum. Notice the pattern: moves 1-3 cleared the top two disks to peg B. Move 4 shifted the big disk. Moves 5-7 relocated the two smaller disks onto the target. This three-part pattern — clear, shift, rebuild — is the recursive structure that scales to any number of disks.

The recursive strategy

To move n disks from the source to the target:

1. Move the top n-1 disks from source to auxiliary (using target as temporary space).
2. Move the remaining largest disk from source to target.
3. Move the n-1 disks from auxiliary to target (using source as temporary space).

Step 1 and step 3 are the same problem with one fewer disk. That is the recursion. The base case is a single disk, which you move directly. Everything else is just this three-step pattern nested inside itself.

This is why the puzzle appears in computer science textbooks. It is one of the clearest real-world examples of a recursive algorithm: the solution to the n-disk problem uses the solution to the (n-1)-disk problem as a building block.

The 2ⁿ - 1 formula

The minimum number of moves for n disks is 2ⁿ - 1. The reasoning comes directly from the recursive strategy:

• 1 disk: 1 move (2¹ - 1 = 1)
• 2 disks: 3 moves (2² - 1 = 3)
• 3 disks: 7 moves (2³ - 1 = 7)
• 4 disks: 15 moves (2⁴ - 1 = 15)
• 5 disks: 31 moves (2⁵ - 1 = 31)
• 7 disks: 127 moves (2⁷ - 1 = 127)
• 10 disks: 1,023 moves (2¹⁰ - 1 = 1,023)

Each additional disk roughly doubles the work. Adding one disk means solving the previous problem twice (once to clear, once to rebuild) plus one move for the new disk. Written as a recurrence: T(n) = 2 × T(n-1) + 1. Solving that gives T(n) = 2ⁿ - 1.

The odd/even shortcut

If you find the recursive approach hard to hold in your head during play, try this mechanical rule instead:

• Odd-numbered moves (1, 3, 5, ...): move the smallest disk.
• Even-numbered moves (2, 4, 6, ...): make the only legal move that does not involve the smallest disk. There will always be exactly one.

The direction the smallest disk travels depends on whether the total number of disks is odd or even. With an odd number of disks (like 3 or 5), the smallest cycles right: source → target → auxiliary → source. With an even number (like 4), it cycles left: source → auxiliary → target → source.

Following this pattern mechanically gives you the optimal solution without needing to think about recursion at all. Useful for the larger disk counts where keeping track of the recursive sub-problems gets tedious.

Difficulty levels

ThePuzzleLabs offers five levels, scaled by disk count:

• Easy (3 disks, 7 moves): Trial and error works fine. Most people solve it in under a minute on their first try.
• Medium (4 disks, 15 moves): Guessing starts to get expensive. The recursive strategy or the odd/even shortcut saves time.
• Hard (5 disks, 31 moves): The middle ground. Long enough to punish sloppy play, short enough to retry quickly.
• Expert (7 disks, 127 moves): Patience matters more than cleverness. Same pattern, longer execution.
• Einstein (10 disks, 1,023 moves): An endurance run. The pattern hasn't changed since 3 disks — you just need to follow it for a lot longer.

Common mistakes

Moving the smallest disk to the wrong peg. The smallest disk needs to cycle in a consistent direction. If it goes right one turn and left the next, you will end up adding unnecessary moves. Pick a direction and stick with it.

Losing track of the sub-problem. With 5+ disks, it is easy to forget whether you are clearing disks to the auxiliary or rebuilding them on the target. If you get confused, the hint system can show you the next optimal move.

Trying to minimise moves on a first attempt. Just complete the puzzle first. Efficiency comes naturally once the pattern is familiar.

Frequently asked questions