How to Solve Tower of Hanoi — Algorithm + Iterative Shortcut

Tower of Hanoi looks intimidating but it’s actually one of the simplest puzzles to solve algorithmically. Here’s the algorithm, why it works, and how to apply it to puzzles up to 64 discs (you won’t finish, but you’ll know what to do).

Short answer on how to solve Tower of Hanoi: move the smallest disc on every odd-numbered move, always in the same direction around the three pegs, and on every even-numbered move make the only legal move that doesn’t touch the smallest disc. That finishes any tower in the minimum 2^N – 1 moves.

The setup

Three pegs. Start: N discs stacked on the leftmost peg (largest on bottom, smallest on top). Goal: move all N discs to the rightmost peg. Rules: move one disc per move; never place a larger disc on a smaller one.

Minimum moves: 2^N – 1 where N is the number of discs. For 3 discs: 7 moves. For 5: 31. For 10: 1,023. For 64 (the temple legend that accompanied the puzzle when Édouard Lucas published it in 1883): 18,446,744,073,709,551,615 — about 585 billion years at one move per second.

Discs	Minimum moves	At one move per second
3	7	7 seconds
4	15	15 seconds
5	31	About half a minute
6	63	About a minute
7	127	About 2 minutes
8	255	About 4 minutes
10	1,023	About 17 minutes
64	18,446,744,073,709,551,615	About 585 billion years

Each extra disc doubles the work and adds one move. That doubling is why the puzzle is a staple of computer science classes: it is the textbook example of exponential growth from a tiny recursive rule (see Tower of Hanoi on Wikipedia).

The recursive algorithm

Suppose you can solve N-1 discs. To solve N:
1. Move N-1 discs from source to spare peg. (Recursive call.)
2. Move disc N from source to target.
3. Move N-1 discs from spare to target. (Recursive call.)

This works because the recursive calls solve smaller versions of the same problem. The base case is N=1: just move the single disc.

In code, the whole Tower of Hanoi algorithm is three lines inside a function that takes the disc count and the three pegs. The roles of the pegs swap on each call: the “spare” for one level becomes the “target” for the level below. That swapping is the only part people find confusing, and it’s why the iterative shortcut below is easier to run by hand.

Why this is the minimum

The largest disc has to move at least once, and it can only move when every other disc is stacked on the third peg. So before its first move you must shift N-1 discs off it (at least the minimum for N-1 discs), and after its last move you must rebuild those N-1 discs on top of it (the same minimum again). That gives: minimum(N) = 2 × minimum(N-1) + 1, with minimum(1) = 1.

The recursive algorithm hits that bound exactly. In it, the smallest disc moves 2^(N-1) times, the next 2^(N-2) times, and the largest only once. Total moves = 2^(N-1) + 2^(N-2) + … + 2^1 + 2^0 = 2^N – 1, the geometric series formula.

The iterative shortcut (without recursion)

Number the discs 1 (smallest) to N (largest). Number the pegs 1, 2, 3.

Rule 1: The smallest disc (disc 1) moves every other turn (odd turns).

Rule 2: Disc 1 moves in a fixed direction. Moving the tower from peg 1 to peg 3: if N is even, it cycles 1 → 2 → 3 → 1 → …; if N is odd, it cycles 1 → 3 → 2 → 1 → …

Rule 3: On even turns, there is only one legal move that doesn’t touch disc 1. Make it.

Following these rules solves the puzzle in 2^N – 1 moves without recursion, and it’s the easiest pattern to run by hand because you never have to track sub-towers.

Two checks that catch mistakes

• The parity check. In the optimal solution a disc never lands directly on a disc of the same parity: odd discs go on even discs or an empty peg, and even discs go on odd discs or an empty peg. If you’re about to put disc 3 on disc 1, something went wrong.
• The binary check. Count your moves from 1. The disc that moves on move m is one more than the number of times m divides evenly by 2. Move 1, 3, 5 and 7 are disc 1; moves 2, 6 and 10 are disc 2; move 4 is disc 3; move 8 is disc 4. The largest disc moves exactly once, on move 2^(N-1), the halfway point.

Worked solution: 3 discs (7 moves)

Three is odd, so the smallest disc travels 1 → 3 → 2 → 1. Pegs are numbered left to right.

1. Disc 1: peg 1 → peg 3
2. Disc 2: peg 1 → peg 2 (the only move that doesn’t touch disc 1)
3. Disc 1: peg 3 → peg 2
4. Disc 3: peg 1 → peg 3 (the largest disc, at the halfway point)
5. Disc 1: peg 2 → peg 1
6. Disc 2: peg 2 → peg 3
7. Disc 1: peg 1 → peg 3

Worked solution: 4 discs (15 moves)

Four is even, so the smallest disc travels 1 → 2 → 3 → 1. The first move is the one most people get wrong: with an even count, disc 1 goes to the middle peg, not the target.

1. Disc 1: 1 → 2
2. Disc 2: 1 → 3
3. Disc 1: 2 → 3
4. Disc 3: 1 → 2
5. Disc 1: 3 → 1
6. Disc 2: 3 → 2
7. Disc 1: 1 → 2 (discs 1–3 now sit on the middle peg)
8. Disc 4: 1 → 3
9. Disc 1: 2 → 3
10. Disc 2: 2 → 1
11. Disc 1: 3 → 1
12. Disc 3: 2 → 3
13. Disc 1: 1 → 2
14. Disc 2: 1 → 3
15. Disc 1: 2 → 3

Notice that moves 1–7 are a 3-disc solution onto the middle peg, and moves 9–15 are a 3-disc solution from the middle peg to the target. That’s the recursive algorithm, visible inside the iterative one.

Practical solving

Our Tower of Hanoi offers 3 to 8 discs plus a 10-disc option. With 5 discs, the optimal solution is 31 moves. Practice the iterative shortcut: at each step, the smallest disc moves in a fixed direction. The remaining move forces itself.

If you make a mistake (wrong direction for disc 1), the minimum moves go up. You can complete the puzzle from any valid state, but the cost rises.

A few things about the controls help. Click or tap a rod to pick up its top disc, then click the destination rod. On a keyboard, 1/2/3 (or A/S/D) select the rods and U or Ctrl/Cmd+Z undoes. Undo takes the move back off the counter, so you can still finish in the minimum after a slip. The Hint button highlights the next optimal move from wherever you are, which is a good way to recover after a slip.

Common mistakes

• Wrong first move. Odd disc count: the smallest disc goes straight to the target peg. Even count: it goes to the spare peg. Get this wrong and the tower ends up on the middle peg.
• Moving the smallest disc twice in a row. It never moves on consecutive turns in the optimal solution; if you just moved it, the next move belongs to another disc.
• Reversing direction. Disc 1 keeps cycling the same way for the whole puzzle. Saying it out loud helps on large towers.
• Overthinking the even moves. There is only ever one legal move that leaves disc 1 alone. Find it and make it.

Practice

Play our Tower of Hanoi. Start at 3 discs (7 moves). Move to 5 (31). Then 7 (127). If you want a real test, 10 discs takes 1,023 moves. Each disc count tests your algorithm execution. When you need a break from the pegs, the Chrome Dino game is one click away.

If you like puzzles with a clean mathematical solution, try Lights Out (our Lights Out guide explains the method) or the sliding puzzle.

Frequently asked questions

What is the fastest way to solve Tower of Hanoi?

Move the smallest disc every other turn in one fixed direction, and in between make the only legal move that doesn’t involve it. This finishes in 2^N – 1 moves, which is the proven minimum.

How many moves does it take to solve Tower of Hanoi with 3 discs?

Seven. With 4 discs it takes 15, with 5 discs 31, and every extra disc doubles the count and adds one.

Which peg should the first disc go to?

It depends on the disc count. With an odd number of discs, move the smallest disc straight to the target peg. With an even number, move it to the spare peg first.

Is Tower of Hanoi always solvable?

Yes. From the starting position, or from any legal position you’ve reached, there is always a way to finish. Mistakes only add moves.

Why is Tower of Hanoi used to teach recursion?

The solution for N discs is built directly from two solutions for N-1 discs plus one move. That makes it a short, visible example of a problem that solves itself by solving smaller copies of itself.

Related reading

• 10 Games Like Tower of Hanoi — Free Logical Puzzles
• How to Solve the 15-Puzzle — Layer-by-Layer Technique
• How to Play Dots and Boxes — Long Chain Theory + Double-Cross