PlayInfoBox

Home /Games /Tower of Hanoi: Rules and the Minimum-Move Solution

Tower of Hanoi: Rules and the Minimum-Move Solution

The Tower of Hanoi looks deceptively simple β€” three pegs and a stack of disks β€” but it hides one of the cleanest examples of recursive logic in classic puzzle design.

The setup: one stack, three pegs

All disks start stacked on one peg in size order, largest on the bottom and smallest on top. The goal is to move the entire stack to a different peg, preserving that same size order.

Rule 1: move only one disk at a time

Each move takes the single top disk from one peg and places it on top of another peg. You can never move more than one disk in a single turn.

Rule 2: a larger disk can never sit on a smaller one

At every point in the game, every peg must have its disks in strict descending size order from bottom to top. A move that would place a bigger disk onto a smaller one is not allowed.

The minimum number of moves is 2^n βˆ’ 1

For n disks, the puzzle can always be solved in exactly 2 to the power of n, minus 1, moves β€” so 3 disks take 7 moves, 4 disks take 15, and 10 disks take 1,023. This is the smallest possible number, not just a typical one.

The solving trick: shrink the problem recursively

To move n disks to the target peg, first move the top nβˆ’1 disks to the spare peg, then move the single largest disk to the target peg, then move the nβˆ’1 disks from the spare peg onto the target peg β€” a strategy that works by treating each smaller stack as its own mini Tower of Hanoi.

A puzzle with a legend attached

The Tower of Hanoi was introduced by French mathematician Γ‰douard Lucas in 1883, reportedly accompanied by a legend about monks moving 64 golden disks and a prophecy that the world would end once they finished. With 64 disks the minimum-move count is over 18 quintillion, which at one move per second would take roughly 585 billion years β€” a fittingly dramatic illustration of exponential growth.

Why the recursive strategy always works

The recursive approach works because the rules of the puzzle never actually care how a smaller sub-stack got positioned on a peg, only that it is in valid descending order. That means any method that correctly relocates nβˆ’1 disks can be reused, unchanged, as a building block for solving n disks, which is exactly why the same simple three-step pattern scales to any number of disks.

Frequently Asked Questions

Why is 2^n βˆ’ 1 the minimum and not just an estimate?

It can be proven that moving the bottom (largest) disk requires first clearing all nβˆ’1 disks above it to a single other peg, and after moving it, those nβˆ’1 disks must be moved again onto it β€” meaning the move count for n disks is always exactly twice the count for nβˆ’1 disks, plus one move, which works out mathematically to 2^n βˆ’ 1.

Does the starting and target peg affect the number of moves needed?

No. The minimum move count depends only on the number of disks, not on which peg you start from or which peg is the target β€” the formula 2^n βˆ’ 1 holds regardless of the specific pegs chosen.