Tower of Hanoi: rules, strategy and recursion

Three pegs, a tower of disks and very few rules: the Tower of Hanoi is a puzzle in which planning matters more than speed. It is also a concrete example of recursion: solving a problem by using the solution to the same problem on a smaller scale.

Open the Tower of Hanoi laboratory: play with 1 to 10 disks

Try a few disks first, then compare your route with the animated solution.

The goal and the rules

The pegs are called A, B and C. Initially all disks are on A, with the largest at the bottom and the smallest on top. Move the entire tower to C; B provides temporary support.

1. Move only one disk at a time.
2. Only the top disk on a peg may be moved.
3. Never place a larger disk on a smaller one. An empty peg can receive any disk.

Number the disks from the smallest, 1, to the largest, n. In the examples, lists are read from bottom to top: [3, 2, 1] is the complete tower, while [] is an empty peg. A move transfers one disk; individual interface clicks are not separate moves.

Start with the simplest case

One disk: one move is enough

Disk 1 goes directly from A to C. Nothing needs to be cleared first: this is the smallest non-empty case of the puzzle.

Two disks: free the larger one first

You cannot move disk 2 immediately because disk 1 is above it. These are the three required moves:

1. Disk 1: A → B.
2. Disk 2: A → C.
3. Disk 1: B → C.

The auxiliary peg is not a final destination: it clears the disk you want to move.

Three disks: all seven moves

To free disk 3, first transfer the small tower [2, 1] from A to B, using C as support. Then move disk 3 to C and finally rebuild [2, 1] above it. The two-disk procedure is unchanged, but the pegs exchange roles.

Row 0 shows the starting position: it is not a move. From row 1 to row 7, each row transfers exactly one disk and follows every rule.

The general strategy: a problem inside the problem

Suppose you already know how to transfer a tower of n−1 disks. To transfer n disks from A to C:

1. Move the top n−1 disks from A to B, using C as support.
2. Move disk n from A to C.
3. Move the n−1 disks from B to C, using A as support.

“Transfer n−1 disks” does not mean moving them as a block: repeat the same recipe with one fewer disk until you reach the simplest case. Every actual move still transfers just one disk.

This pseudocode makes the roles of the pegs explicit. With zero disks there is nothing to move: this is the condition that stops the recursive calls.

Hanoi(n, source, target, auxiliary):
    if n = 0: return
    Hanoi(n−1, source, auxiliary, target)
    move disk n from source to target
    Hanoi(n−1, auxiliary, target, source)

The initial call is Hanoi(n, A, C, B). Each call changes the roles of source, target and auxiliary peg, not the rules of the puzzle.

Why can no solution beat 2ⁿ − 1?

Let M(n) be the minimum number of moves needed to transfer a complete tower of n disks between two pegs. Before the largest disk moves for the first time, all the others must be together on the third peg: this requires at least M(n−1) moves. The largest disk needs at least one move. After its last arrival on the target peg, the smaller disks must be transferred from the third peg onto it: at least another M(n−1) moves. Detours cannot remove these two compulsory transfers.

The strategy above performs exactly these three stages without additional moves. It therefore reaches the lower bound:

M(0) = 0
M(n) = 2 × M(n−1) + 1 = 2ⁿ − 1

To check the last equality, replace M(n−1) with 2ⁿ⁻¹ − 1: this gives 2 × (2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1. The base case M(0) = 0 completes the induction argument.

Adding a disk almost doubles the work. At one move per second, 10 disks take 1023 seconds, or 17 minutes and 3 seconds, without pauses. The move count grows exponentially: a short rule can describe a very long procedure.

How to use the laboratory

Enter the interactive Tower of Hanoi laboratory

• Choose between 1 and 10 disks: all levels are available immediately.
• Tap the source peg, then the target peg. With a keyboard, use Tab, Enter or Space.
• Use “Undo move” to reverse the last transfer and “Restart level” to start over.
• “Hint” suggests without moving; “One step” performs one move; “Start solution” shows an animated route at your chosen speed.
• The guided solution continues from the current position, even after a different route of your own. “Pause” allows a move already in progress to finish.

“Minimum from the start” concerns the initial tower; “Minimum still needed” concerns the current position. After a detour, moves already made plus moves still needed can exceed the initial minimum. Records update only for manual games without assistance and stay in this browser: they are not sent to the website.

Three challenges before revealing the answers

1. What is the minimum number of moves for four disks?

2. With three disks going from A to C, why should disk 1 start by moving from A to C rather than A to B?

3. You have made 4 moves and the laboratory says at least 5 more are needed. Can you finish in 7 moves overall?

What does this puzzle teach?

The Tower of Hanoi shows how to break down a task, recognize a subproblem and define a stopping condition. Recursion is not a trick for skipping steps: it is a precise way to organize them while respecting the same constraint on every move.

Reference for the rules, recursive strategy and minimum move count: NIST — Dictionary of Algorithms and Data Structures: Towers of Hanoi.