Tower of Hanoi
The legendary mathematical puzzle invented by Édouard Lucas in 1883. Transfer all disks from source to destination peg with optimal minimal moves.
Tower of Hanoi
Move all disks to the rightmost peg. Larger disks cannot be placed on smaller ones.
Click a peg to select its top disk, then click another peg to drop it. Minimum possible moves: 31.
The Recurrence Formula: M(n) = 2ⁿ - 1
The Tower of Hanoi is a classical mathematical puzzle demonstrating recursive decomposition and exponential time complexity. To move a tower of n disks from a starting peg to a target peg using three pegs, the exact minimal move sequence is governed by the recurrence relation M(n) = 2M(n-1) + 1, resolving to the closed-form equation M(n) = 2ⁿ - 1.
Because each additional disk doubles the total number of required moves plus one, the solution space scales exponentially. Any mistake or backtracking move instantly drops the player's move efficiency score below the theoretical optimal threshold.
How to Solve Tower of Hanoi in 6 Minimal Steps
Understand the Inviolable Rules
Move one disk at a time between three pegs (Source, Auxiliary, Destination). A larger disk may never rest on top of a smaller disk at any stage.
Identify the Recursive Base Case
To move a tower of n disks from Peg A to Peg C, you must first move the top n-1 disks to Peg B, move disk n to Peg C, and transfer the n-1 disks from B to C.
Determine the First Move Parity
If the total number of disks is odd, move the smallest disk directly to the Destination peg. If even, move the smallest disk to the Auxiliary peg.
Follow the Alternating Step Cadence
Every alternate move must involve the smallest disk. On every odd turn, shift the smallest disk; on every even turn, make the only other legal move available.
Never Place Larger Disks on Smaller Ones
Constantly verify peg hierarchy before releasing a disk. Backtracking due to an illegal move adds penalty turns that corrupt minimal efficiency.
Complete the Sequence in 2ⁿ - 1 Moves
Reach the target Destination peg with zero extraneous moves, achieving 100% minimal move efficiency (7 moves for 3 disks, 15 for 4, 31 for 5).
Recursive Algorithmic Thinking
Working Memory & Lookahead Planning
Inhibition Control & Error Prevention
Cognitive Assessment Standard
Disk Count vs. Minimal Move Recurrence Analysis
| Disks (n) | Formula (2ⁿ - 1) | Minimal Moves | First Move Target | Estimated Solving Time |
|---|---|---|---|---|
| 3 Disks | 2³ - 1 | 7 | Destination (Peg C) | 5 – 10 seconds |
| 4 Disks | 2⁴ - 1 | 15 | Auxiliary (Peg B) | 15 – 30 seconds |
| 5 Disks | 2⁵ - 1 | 31 | Destination (Peg C) | 45 – 90 seconds |
| 6 Disks | 2⁶ - 1 | 63 | Auxiliary (Peg B) | 2 – 4 minutes |
| 7 Disks | 2⁷ - 1 | 127 | Destination (Peg C) | 5 – 10 minutes |
Tower of Hanoi Efficiency Tiers (Move Efficiency Ratio)
Efficiency is measured by dividing the theoretical minimal move count by your actual moves taken. Benchmark your score:
Frequent circular backtracking and accidental disk shuffling. Loses track of the destination sub-goal mid-sequence.
Understands recursive sub-towers. Occasional 2-to-4 move deviations when shifting larger intermediate base plates.
Flawless alternating smallest-disk cadence. Near-perfect memory retention across 5+ disk configurations.
Exact theoretical minimum (e.g. exactly 31 moves for 5 disks). Zero wasted clicks and rapid mechanical execution.
4 Golden Rules for 100% Minimal Move Efficiency
Count your total disks. If the total count is odd (3, 5, 7), place disk 1 onto Peg C (Destination). If even (4, 6), place disk 1 onto Peg B (Auxiliary). This single choice guarantees a minimal path.
Every other move in the entire game involves Disk 1. Never move a larger disk twice in a row. Smallest disk, other disk, smallest disk, other disk—this rhythm removes decision paralysis.
On even-numbered turns (when moving a disk other than Disk 1), there is always exactly one legal move that does not undo the immediately preceding placement. Make that solitary move.
Treat the top 3 disks as a single cohesive pyramid that needs to park on the temporary peg before moving disk 4. Chunking eliminates the mental strain of tracking individual disks.
Frequently Asked Questions About Tower of Hanoi
What is the theoretical minimum number of moves to solve Tower of Hanoi?
For a tower of n disks, the exact minimum number of moves is given by the recurrence formula: M(n) = 2ⁿ - 1. For 3 disks, the minimum is 7 moves (2³ - 1); for 4 disks, 15 moves; for 5 disks, 31 moves; and for 7 disks, 127 moves. Any additional move represents an inefficiency or backtracking error.
What are the three inviolable rules of Tower of Hanoi?
Rule 1: Only one single disk may be moved during any turn. Rule 2: Each move consists of picking up the top disk from one peg and sliding it onto another peg. Rule 3: No larger disk may ever be placed on top of a smaller disk at any point in the game.
Why is Tower of Hanoi the quintessential teaching problem for recursion?
Solving n disks naturally breaks down into three self-similar subproblems: 1) Move the top n-1 disks from Source to Auxiliary peg. 2) Move the single largest disk directly from Source to Destination peg. 3) Move the n-1 disks from Auxiliary to Destination peg. This divide-and-conquer structure is the gold standard for teaching mathematical induction and recursive call stacks.
What is the mythical origin story of the Tower of Brahma?
When French mathematician Édouard Lucas published the puzzle in 1883 under the pseudonym N. Claus de Siam, he included an ancient Hindu legend. The myth claimed that Brahmin priests in a temple at Kashi were transferring 64 golden disks across three diamond needles. Legend held that when the priests completed the 2⁶⁴ - 1 moves (over 18.4 quintillion moves, taking 585 billion years at 1 move per second), the universe would end.
How does the iterative solution work using binary Gray code?
Tower of Hanoi can be solved mechanically without recursion using binary Gray code or simple parity rules. On every odd-numbered move (1st, 3rd, 5th, etc.), you always move the smallest disk in a fixed direction (clockwise for odd disk counts, counterclockwise for even disk counts). On even-numbered moves, you make the only other legal move available.
How does solving Tower of Hanoi improve executive cognitive planning?
Tower of Hanoi is heavily utilized in neuropsychological assessments (such as the Delis-Kaplan Executive Function System) to measure frontal lobe function. It evaluates goal-directed behavior, prospective memory, inhibition of impulsive moves, and long-range algorithmic planning.
What is the Frame-Stewart algorithm for Tower of Hanoi with 4 or more pegs?
When played with 4 pegs (Reve's Puzzle) or more, the minimum move problem becomes significantly more complex. The Frame-Stewart algorithm provides the presumed optimal solution by partitioning the n disks into two groups (k and n-k), moving k disks using all pegs, and the remainder with fewer pegs, reducing the move count drastically compared to 3 pegs.
Explore More Logic & Mathematical Puzzles
Test your algorithmic reasoning, working memory, and constraint satisfaction across our puzzle suite: