Tower of Hanoi: solve it in the fewest moves

Three pegs and one rule about size

Move every disk to the right-hand peg. You can lift only the top disk of a peg, move one disk at a time, and place it on an empty peg or a larger disk. A larger disk can never sit on a smaller one.

Here you can start with a complete tower of three, four, five, six or seven disks on the left. Scrambled is different: five disks begin across the three pegs. The destination stays the same, but the shortest route depends on that particular arrangement.

You can drag a top disk, select a disk and its destination, or use the keyboard. Keys 1, 2 and 3 select pegs. The arrow keys and Enter offer another way to move between them. A refused move leaves the puzzle where it was.

Why the minimum doubles, then adds one

For a full tower, first put every disk except the largest on the spare peg. Move the largest to the destination. Then bring the smaller tower onto it. Before the largest can reach the destination, both it and that peg must be clear of smaller disks, so the preparation cannot be skipped.

If the smaller tower takes T moves, the whole job takes T + 1 + T. Starting from one disk and one move gives 3, 7, 15, 31, 63 and 127 moves for two through seven disks. Written as a formula, the full-tower minimum is 2ⁿ − 1, where n is the number of disks.

Cambridge's discrete mathematics notes give this recursive construction and trace the puzzle to Édouard Lucas in 1883. The formula describes a complete starting tower on one peg, not every partly moved or scrambled position.

Work through three disks

Call the disks small, medium and large. To move the full tower from left to right, first make room for the large disk:

• Move small from left to right, medium from left to middle, then small from right to middle. The two smaller disks now form a tower on the spare peg.
• Move large from left to right. This is the move the first three were preparing.
• Move small from middle to left, medium from middle to right, then small from left to right.

That is three moves, one move, then three moves: seven altogether. For four disks, the same plan uses a three-disk tower as its smaller job. You do not need to invent a completely different sequence.

What this practice records

The result shows your moves, the fewest possible for the starting deal, hints used and active time. The minimum is calculated from the legal puzzle positions, not from other players' results. Scrambled deals receive their own exact minimum; they are not automatically assigned 31 because they contain five disks.

Undo removes a move from the displayed count. The finishing number therefore describes the path left after your undos, not every movement you tried. The clock starts with your first move and pauses while the tab is in the background. Time spent considering the untouched starting board is not included.

A hint makes one move along a shortest route from your current position. That move counts, and hint use stays recorded even if you undo it. A hinted solution can still be saved locally as solved, but it is excluded from solving-time comparisons. Leaving an unsolved deal saves no completed result.

Read these details together. Fifteen moves with a hint is a different account of a four-disk solve from fifteen without one. Neither result, by itself, tells you how you will approach an unfamiliar puzzle.

What researchers found interesting about it

In The functional equivalence of problem solving skills (1975), Herbert Simon used the Tower of Hanoi to examine different ways people could solve the same problem. He described four broad classes of strategy, with different demands on memory, perception and learning.

The useful point for this page is modest: reaching the same destination need not mean doing the same mental work. Someone following a learned recursive method and someone finding a route move by move may finish with similar numbers. Our move counter cannot tell which process produced them, and it is not an assessment of general planning ability.

Practice the next subgoal, not the whole sequence

Before moving, name the largest disk that needs to go somewhere next. Ask where the smaller tower must wait so that move becomes legal. Keep that temporary destination in mind; moving a small disk away from the final peg can be exactly the right preparation.

If you get stuck, use one hint and explain what it made possible before asking for another. Resetting the same deal lets you try that subgoal again. Treat the reset as another attempt at a familiar position, not a new independent measurement.

The Move the smaller tower first lesson illustrates this structure. The Tower of Hanoi practice starts with three disks and lets you choose a larger tower or a scrambled deal when you want another problem.