About the Tower of Hanoi | Rules, 2ⁿ−1, and the Legend

Three pegs and a cone of disks

The board has three pegs. The disks are all different sizes, and they slide onto the pegs. At the start the whole set sits on one peg, ordered by size, largest at the bottom and smallest on top, so the stack is a cone. The goal is to move that whole tower onto another peg.

Wooden Tower of Hanoi puzzle with stacked disks — Wooden Tower of Hanoi puzzle. Photo: PranavAmbhore, CC BY-SA 3.0

The three rules

1. Move only one disk at a time. 2. A move takes the top disk of a stack and sets it on another stack, or on an empty peg. 3. A larger disk may never sit on a smaller disk. Those three rules are the whole game. With them, every legal position is a way of splitting the disks across the pegs while each peg stays sorted.

The shortest solution is 2ⁿ − 1

The fewest moves that solve a tower of n disks is 2ⁿ − 1. One disk takes 1 move. Two disks take 3. Three take 7, four take 15, and five take 31. Each new disk doubles the previous solution and adds the one move that carries that largest disk: if n − 1 disks take T moves, then n disks take 2T + 1. That recurrence is exactly 2ⁿ − 1. Eight disks, the largest tower in the PictorX app, take 255 moves. There is no shorter legal path.

How the recursion works

To move n disks from the start peg to the goal peg, using the remaining peg as spare: 1. Move the top n − 1 disks from the start peg to the spare peg. 2. Move the largest disk from the start peg straight to the goal peg. 3. Move the n − 1 disks from the spare peg onto the goal peg, on top of the largest disk. Step 2 is legal because the largest disk may sit on any peg. Steps 1 and 3 are the same puzzle, one disk smaller. The call bottoms out at a single disk, which moves once. Unrolling it produces the 2ⁿ − 1 moves, and no step ever places a larger disk on a smaller one.

Giant outdoor Tower of Hanoi puzzle with people climbing disks — Giant Tower of Hanoi at Domaine de Chanteloup. Photo: Als33120, CC BY-SA 4.0

The legend of 64 golden disks

The French mathematician Édouard Lucas introduced the puzzle in 1883. With it he told a legend about an Indian temple at Kashi Vishwanath, where priests move a stack of 64 golden disks under these same rules. When the last move is made, the legend says, the world will end. Sixty-four disks take 2⁶⁴ − 1 moves: 18,446,744,073,709,551,615. At one perfect move per second, day and night, that is about 585 billion years. The priests are not going to finish.

Portrait of the French mathematician Edouard Lucas — Edouard Lucas (1842-1891), who introduced the puzzle in 1883. Public domain

Play it in PictorX

Open Tower of Hanoi and a tower of four disks is already on the start peg. Fifteen moves is the minimum. Drag the top disk to another peg, or click a peg and then the peg you want. Keys 1, 2, and 3 do the same. A larger disk on a smaller one is refused. Disks runs from 1 to 8, so you can check 1, 3, 7, 15, 31, 63, 127, and 255 against the formula. Step plays one move of a shortest solution. Solve plays the rest. Watch 3 disks is the recursive strategy in motion. Undo and Redo walk back through your moves. Save a PNG, or open the board in the PictorX editor.

Frequently asked questions

What are the rules of the Tower of Hanoi?

Move one disk at a time. Take the top disk of a peg and place it on another peg. Never put a larger disk on a smaller one. The whole tower starts on one peg and must end on another.

How many moves does the shortest solution take?

2ⁿ − 1. One disk is 1 move, two disks are 3, three are 7, four are 15, and five are 31. Each added disk doubles the previous solution and adds one move.

Who invented the Tower of Hanoi?

Édouard Lucas, a French mathematician, introduced it in 1883. The story of priests and 64 golden disks at Kashi Vishwanath is the legend he attached to the puzzle.

How long would 64 disks take?

2⁶⁴ − 1 moves, which is 18,446,744,073,709,551,615. At one move per second that is about 585 billion years.