Tower of Hanoi: Rules, the Minimum-Moves Formula and How to Solve It

The Tower of Hanoi is a puzzle with three pegs and a stack of disks of different sizes. The goal is to move the whole stack from one peg to another, one disk at a time, without ever putting a bigger disk on a smaller one. The fewest moves it can be done in, for n disks, is 2^n − 1 (two multiplied by itself n times, minus one). That's 7 moves for 3 disks, 15 for 4, and 1,023 for 10.

The trick to solving it is a single idea that repeats: to move a tower of n disks, first move the n − 1 disks on top out of the way, then move the biggest disk, then put the n − 1 disks back on top of it. This guide explains that idea, shows full move lists, gives a no-thinking-required method you can follow by hand, and covers the puzzle's surprising links to binary numbers, its 1883 origin and its use in psychology research.

The Rules of the Tower of Hanoi

The puzzle starts with all the disks stacked on one peg, largest at the bottom and smallest at the top, like a cone. Call the pegs A (start), B (spare) and C (goal).

1. Move one disk at a time.
2. Only the top disk of a stack can move. You lift it off one peg and drop it onto another.
3. Never place a larger disk on a smaller one. A disk can go on an empty peg or on a larger disk.

You win when the whole stack sits on peg C in its original order. Moving it to peg B counts too in most versions, since the pegs are interchangeable, but we'll use C as the goal throughout.

Number the disks

To talk about moves, number the disks by size: disk 1 is the smallest, disk 2 the next, and so on up to disk n, the biggest. A move like "1 A→C" means "move disk 1 from peg A to peg C."

The Minimum-Moves Formula: 2^n − 1

Here's the formula in a table, with the time it would take at one move per second. We computed each value directly.

Disks (n)	Minimum moves (2^n − 1)	Time at one move per second
1	1	1 second
2	3	3 seconds
3	7	7 seconds
4	15	15 seconds
5	31	31 seconds
6	63	about 1 minute
8	255	about 4 minutes
10	1,023	about 17 minutes
15	32,767	about 9 hours
20	1,048,575	about 12 days
25	33,554,431	about 388 days
30	1,073,741,823	about 34 years
64	18,446,744,073,709,551,615	about 585 billion years

Each extra disk roughly doubles the work. That's what makes the puzzle such a good illustration of exponential growth: a handful of disks is a quick game, and a few dozen is beyond any human lifetime.

Why the formula works

Wolfram MathWorld's Tower of Hanoi entry gives the key relationship: if h(n) is the minimum number of moves for n disks, then h(n) = 2 × h(n − 1) + 1, with h(1) = 1. Here's why, in plain terms.

• You can't do it in fewer. The biggest disk has to move at least once. At the moment it moves, it must be alone on its peg (nothing on top of it), and the peg it moves to must be empty (nothing smaller can be under it). So all n − 1 smaller disks must be stacked on the third peg. Getting them there takes at least h(n − 1) moves. After the big disk moves, those n − 1 disks still have to end up on top of it, which takes at least h(n − 1) more. That's at least 2 × h(n − 1) + 1.
• You can do it in exactly that many. The recursive method below uses exactly h(n − 1) + 1 + h(n − 1) moves.

Now check the closed formula. If h(n − 1) = 2^(n − 1) − 1, then h(n) = 2 × (2^(n − 1) − 1) + 1 = 2^n − 2 + 1 = 2^n − 1. Starting from h(1) = 1 = 2 − 1, that pattern carries on forever. Numbers of the form 2^n − 1 are called Mersenne numbers, as MathWorld notes.

How to Solve the Tower of Hanoi: The Recursive Method

To move n disks from A to C:

1. Move the top n − 1 disks from A to B (using C as the spare).
2. Move disk n from A to C.
3. Move the n − 1 disks from B to C (using A as the spare).

Steps 1 and 3 are smaller versions of the same puzzle, so you apply the same three steps to them, and so on down to a single disk, which you just move. Programmers call this recursion: a method that solves a problem by using itself on a smaller version.

The 3-disk solution, move by move

Move	Disk	From	To	What's happening
1	1	A	C	Start moving disks 1 and 2 out of the way, onto B
2	2	A	B
3	1	C	B	Disks 1 and 2 now sit on B
4	3	A	C	The big disk moves to the goal
5	1	B	A	Now move disks 1 and 2 from B onto C
6	2	B	C
7	1	A	C	Done in 7 moves

Notice the shape: moves 1 to 3 are a 2-disk solution (A to B), move 4 is the big disk, and moves 5 to 7 are another 2-disk solution (B to C).

The 4-disk solution

Here are all 15 moves for four disks, from A to C. We generated and checked the list by computer.

1 A→B, 2 A→C, 1 B→C, 3 A→B, 1 C→A, 2 C→B, 1 A→B, 4 A→C, 1 B→C, 2 B→A, 1 C→A, 3 B→C, 1 A→B, 2 A→C, 1 B→C

The first seven moves shift disks 1 to 3 onto peg B, move 8 sends disk 4 to C, and the last seven bring disks 1 to 3 across from B to C. Notice that the very first move is different from the 3-disk case: with 4 disks, disk 1 goes to B first, not C. That's the most common way people get off on the wrong foot, and the next method explains why.

The Easy Hand Method: Two Moves That Alternate

Recursion is elegant, but it's hard to keep track of in your head with five or six disks. Here's a method that needs no memory at all. We tested it by computer against the recursive solution for every stack from 1 to 9 disks, and it produces the identical, optimal sequence.

1. On odd-numbered moves (1st, 3rd, 5th, …), move the smallest disk one step around a fixed circle:
   • If the number of disks is odd: A → C → B → A → …
   • If the number of disks is even: A → B → C → A → …
2. On even-numbered moves, make the only legal move that doesn't involve the smallest disk. There will always be exactly one: of the two pegs the smallest disk isn't on, move the smaller top disk onto the other peg.

That's it. Alternate these two steps and the tower walks itself over to peg C in the minimum number of moves.

Try it on 3 disks

Three is odd, so disk 1 cycles A → C → B → A. Move 1: disk 1 A→C. Move 2: the pegs without disk 1 are A (top disk 2) and B (empty), so disk 2 goes A→B. Move 3: disk 1 C→B. Move 4: the pegs without disk 1 are A (disk 3) and C (empty), so disk 3 goes A→C. Move 5: disk 1 B→A. Move 6: the pegs without disk 1 are B (disk 2) and C (disk 3), and disk 2 is smaller, so disk 2 goes B→C. Move 7: disk 1 A→C. Solved, and it matches the table above exactly.

Watching the Pegs: A 4-Disk Walkthrough

Move lists are easier to follow when you can see the pegs. This table shows what's on each peg after every move of the 4-disk solution, listed from bottom to top (a dash means the peg is empty). We generated it by simulating every move and checking that no disk ever landed on a smaller one.

Move	Disk and direction	Peg A	Peg B	Peg C
Start	-	4 3 2 1	-	-
1	1 A→B	4 3 2	1	-
2	2 A→C	4 3	1	2
3	1 B→C	4 3	-	2 1
4	3 A→B	4	3	2 1
5	1 C→A	4 1	3	2
6	2 C→B	4 1	3 2	-
7	1 A→B	4	3 2 1	-
8	4 A→C	-	3 2 1	4
9	1 B→C	-	3 2	4 1
10	2 B→A	2	3	4 1
11	1 C→A	2 1	3	4
12	3 B→C	2 1	-	4 3
13	1 A→B	2	1	4 3
14	2 A→C	-	1	4 3 2
15	1 B→C	-	-	4 3 2 1

A few things to notice as you read down the table:

• Move 7 is a checkpoint. Disks 1 to 3 are stacked neatly on B, and disk 4 sits alone on A. That's the end of the first "move n − 1 disks out of the way" stage.
• Move 8 is the only time disk 4 moves. It's exactly the middle move, with 7 moves before it and 7 after.
• Disks visit the goal peg early and leave again. Disk 2 lands on C at move 2 and leaves at move 6. That's not a mistake; it's part of the plan.
• Disk 1 follows a fixed circle. With 4 disks (an even number), disk 1 goes A→B, B→C, C→A, A→B and so on, exactly as the hand method says.

The Binary Counting Trick

The Tower of Hanoi hides a beautiful link to binary numbers, the base-2 system computers use.

Which disk moves next?

Write the move number in binary and count the zeros at the right-hand end. Add 1, and that's the disk to move. We verified this rule for every move of every stack up to 9 disks.

Move	Binary	Zeros at the end	Disk moved
1	001	0	1
2	010	1	2
3	011	0	1
4	100	2	3
5	101	0	1
6	110	1	2
7	111	0	1

So the sequence of disks goes 1, 2, 1, 3, 1, 2, 1 for three disks, and 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 for four. This pattern is sometimes called the "ruler sequence," because it matches the heights of the tick marks on a ruler marked in halves, quarters, eighths and sixteenths. MathWorld describes the same pattern as the "binary carry sequence" plus one.

How many times does each disk move?

The smallest disk moves on every other turn, the next disk on every fourth, and so on. In an n-disk solution, disk k moves 2^(n − k) times. With 5 disks, disk 1 moves 16 times, disk 2 moves 8 times, disk 3 moves 4, disk 4 moves 2 and disk 5 moves once. That's 16 + 8 + 4 + 2 + 1 = 31 = 2^5 − 1, which is another way to see the formula.

The Gray code connection

A Gray code is a way of listing binary numbers so that each one differs from the last in exactly one digit. MathWorld's Gray code entry gives the 3-bit reflected version as 000, 001, 011, 010, 110, 111, 101, 100, and says the code is closely related to the Tower of Hanoi. Here's the link: number the digit positions from the right as 1, 2, 3. Going down the list, the digit that changes is position 1, then 2, then 1, then 3, then 1, 2, 1. That's exactly the sequence of disks in the 3-disk solution.

The Legend and History of the Puzzle

Lucas and his 1883 puzzle

MathWorld credits the puzzle to the French mathematician Édouard Lucas in 1883. Lucas wrote about it in volume 3 of his Récréations mathématiques, which you can read in the Internet Archive's scan of the 1893 Gauthier-Villars edition. In it he playfully credits the game to "Professor N. Claus (de Siam)" of the "Li-Sou-Stian" college. Shuffle the letters and you'll see the joke: N. CLAUS DE SIAM uses exactly the letters of LUCAS D'AMIENS, and LI-SOU-STIAN uses exactly the letters of SAINT LOUIS. Lucas was signing his own work in disguise.

The temple legend

Lucas also tells a legend that's been attached to the puzzle ever since. In the great temple at Benares, he writes, 64 gold disks sit on one of three diamond needles, and priests move them one at a time according to Brahma's rules. When the last disk is in place, the tower and the priests will fall and the world will end.

The legend is a story, but the math in it is real. Lucas gives the number of moves for 64 disks as 18,446,744,073,709,551,615, which is exactly 2^64 − 1, and says it would take more than five billion centuries at one move per second. Check it: there are about 31,557,600 seconds in a year (using 365.25 days), and 18,446,744,073,709,551,615 ÷ 31,557,600 comes to about 584.5 billion years, or about 5.8 billion centuries. Lucas also points out that this is the same number as the grains of wheat in the old story of doubling grains on each square of a chessboard. So no need to worry about the priests.

Other names

The puzzle is also called the Tower of Brahma, and MathWorld notes it appears as a "Lucas Tower" intelligence test for apes in the 2011 film Rise of the Planet of the Apes.

Beyond Three Pegs: The Four-Peg Puzzle

Add a fourth peg and the puzzle gets much faster, and much harder to analyze. With a spare peg, you can park disks in two places at once. Here are the minimum moves for four pegs, which we confirmed by having a computer search every possible position for stacks of up to 8 disks:

Disks	3 pegs (2^n − 1)	4 pegs (minimum)
1	1	1
2	3	3
3	7	5
4	15	9
5	31	13
6	63	17
7	127	25
8	255	33

The standard method for more pegs is the Frame-Stewart algorithm, named for J. S. Frame and B. M. Stewart, whose solutions appeared in the American Mathematical Monthly in 1941. The idea: move some number k of the top disks to a spare peg using all four pegs, move the rest using only three pegs (since one is now occupied), then bring the k disks back on top. You choose k to make the total as small as possible. It matched our computer search for every size we tested.

Proving that Frame-Stewart is really the best possible turned out to be hard. MathWorld reports that Thierry Bousch proved it optimal for four pegs in 2014, and that for five or more pegs, optimality is still a conjecture. It's a striking example of how a toy-sized puzzle can lead to problems that take decades to settle.

The Tower of Hanoi in Psychology and Brain Research

Because it rewards planning ahead, the Tower of Hanoi became a standard tool for studying problem-solving. To solve it efficiently, you have to set a goal (move the big disk), notice that a subgoal stands in the way (clear the smaller disks off it), and sometimes make moves that seem to go backward, like moving disks away from the goal peg.

In a 1995 study in Neuropsychologia, Goel and Grafman tested 20 adults with damage to the prefrontal cortex (the front part of the brain) on the Tower of Hanoi. They did significantly worse than a comparison group, and the gap wasn't explained by general intelligence, memory or the size of the injury. Both groups seemed to use the same basic strategy. The authors argued that the patients' main trouble wasn't planning far ahead but resolving conflicts between a goal and a subgoal, such as when the right move means temporarily moving a disk away from where it ultimately needs to go.

A close cousin of the puzzle grew out of the same research area. In 1982, Tim Shallice published "Specific impairments of planning" in the Philosophical Transactions of the Royal Society, describing a task designed to depend heavily on planning, on which patients with damage to the left front of the brain did poorly. That line of work is linked to a task now widely known as the Tower of London, a cousin of the Tower of Hanoi that's often used alongside it.

These are research tools used by trained professionals, not do-it-yourself tests. If you're curious about how puzzles relate to thinking skills more generally, our article on whether puzzles are good for the brain looks at what the evidence does and doesn't show.

More Patterns Worth Knowing

• Total positions. Each disk can be on any of the three pegs, and for any choice of pegs there's only one legal way to stack them (largest at the bottom). So there are 3^n legal positions: 27 for 3 disks and 81 for 4.
• The optimal path is a tiny slice of them. The 2^n − 1 moves of the best solution visit 2^n positions, counting the start. For 8 disks, that's 256 of the 6,561 possible positions.
• The smallest disk never sits still twice in a row. In the optimal solution, every other move is the smallest disk.
• Odd and even disks rotate in opposite directions. If you watch the solution, the odd-numbered disks all circle the pegs one way and the even-numbered disks circle the other way. That's why the direction of the smallest disk depends on whether the total is odd or even.
• Never move the same disk twice in a row. In an optimal solution you never do, since the second move would either undo the first or could have been combined with it.

Variations to Try

Once the standard puzzle feels easy, small rule changes make it fresh again.

Neighbors only

Put the three pegs in a row and allow moves only between neighboring pegs: A to B, B to A, B to C or C to B, but never straight from A to C. Every disk now has to pass through the middle peg. The minimum number of moves jumps to 3^n − 1. We confirmed this by computer search for 1 to 6 disks: the minimums were 2, 8, 26, 80, 242 and 728, exactly 3^n − 1 each time. Interestingly, that's one less than the total number of positions, 3^n, which means the best solution passes through every legal arrangement of the disks exactly once.

Start from the middle

Ask a friend to set up a legal position partway through (disks spread over all three pegs, but never a big disk on a small one). Your job is to gather everything onto one peg. The same thinking applies: find the biggest disk that isn't already in place, and work out where the smaller disks need to be for it to move.

Race the formula

Time yourself on 3, 4, 5 and 6 disks and count every move. The goal isn't speed so much as hitting 7, 15, 31 and 63 exactly. If your count is higher, you took a detour, and the move table above can help you find where.

The Puzzle as a Computer Program

The Tower of Hanoi is one of the first examples many programming students meet when they learn recursion, because the whole solution fits in a few lines. Here's the logic in plain English, for a function that moves n disks from a "from" peg to a "to" peg using a "spare" peg:

1. If n is 0, there's nothing to do, so stop.
2. Otherwise, move n − 1 disks from "from" to "spare," using "to" as the helper.
3. Move disk n from "from" to "to," and write the move down.
4. Move n − 1 disks from "spare" to "to," using "from" as the helper.

That's the program we used to generate and check every move list in this article. Notice that the function calls itself twice, each time with one fewer disk. Each call makes two more calls, which make two more, and so on, so the total amount of work doubles with every disk you add. That's the 2^n − 1 formula showing up again, this time as running time. It's a gentle first lesson in why some problems get out of hand quickly as they grow.

The alternating hand method from earlier is the "iterative" version of the same solution: instead of a function calling itself, it's a simple loop that repeats two rules. Both produce exactly the same moves, which we confirmed for every stack size from 1 to 9 disks.

Using the Tower of Hanoi With Kids and Groups

The puzzle works for a wide range of ages because you can scale it by adding disks. Three disks is a good first challenge, four is satisfying, and five or more takes real concentration.

• Start with 2 disks. It takes only 3 moves, and it shows the core idea: the small disk gets out of the way, the big disk moves, and the small disk comes back.
• Ask for predictions. After solving 1, 2 and 3 disks (1, 3 and 7 moves), ask how many 4 disks will take. Spotting "double it and add one" is a real mathematical discovery.
• Work in pairs. One person moves while the other calls out moves using the hand method. Then swap.
• Connect it to binary. For older learners, counting moves in binary and predicting which disk moves next is a memorable way to practice base 2.

Common Mistakes and How to Avoid Them

• Starting the smallest disk in the wrong direction. With an odd number of disks, the first move goes straight to the goal peg. With an even number, it goes to the spare peg. Get this wrong and you'll finish on the wrong peg (or take extra moves to fix it).
• Losing track halfway. Use the alternating method: odd moves are always the smallest disk in its fixed direction, and even moves are always the only other legal move.
• Moving the same disk twice in a row. If you catch yourself doing it, you've wasted a move.
• Forgetting that the goal peg is just another peg. In the middle of the solution, disks will sit on the goal peg and leave again. That's normal.
• Counting moves wrong. If your count for n disks isn't 2^n − 1, you took a detour somewhere.

Try It Yourself

Make your own set

You don't need a wooden toy. Cut four or five paper squares or circles of different sizes, number them, and draw three circles on a sheet of paper as "pegs." Coins of different sizes work too. Stack them on the left circle and start moving.

Challenges

1. Solve 4 disks in 15 moves. Remember: with 4 disks (even), the first move is disk 1 to the spare peg, B.
2. Predict the 12th move of a 4-disk game. Use the binary trick. Twelve is 1100 in binary, with two zeros at the end, so it's disk 3. Check it against the 4-disk move list above (move 12 is 3 B→C).
3. Solve 5 disks in 31 moves. Five is odd, so disk 1 starts by going straight to C.
4. Find the halfway point. In any optimal solution, the middle move is the one where the biggest disk moves. For 5 disks, which move number is that? (Answer: move 16, since 15 moves come before it and 15 after.)

Wrap-Up: Puzzles That Teach You to Think Ahead

The Tower of Hanoi packs a lot into a few disks: a clean rule set, a formula you can prove in two lines, a recursive solution, a mindless-but-perfect hand method, and links to binary numbers and brain research. Once you've mastered it, other planning puzzles feel a little easier. If you enjoy step-by-step logic, mazes are a natural next stop; try our printable mazes or the roundup of games like sudoku. For more brainy math, see the mathematics of sudoku, and for puzzle ideas for learners at home, try puzzles for homeschool and puzzles for senior brain games.

And when you want a puzzle on paper, our free puzzle maker lets you type your own words or pick a theme, choose a puzzle type, and print it with an answer key.

Five Slip-Ups and How to Fix Them

This table pairs each common mistake with what goes wrong and a simple fix.

Slip-up	What goes wrong	The fix
Starting the smallest disk in the wrong direction	You finish on the wrong peg or take extra moves to fix it	With an odd number of disks the first move goes straight to the goal peg, and with an even number it goes to the spare peg
Losing track halfway	You can't tell which move comes next	Use the alternating method: odd moves are always the smallest disk in its fixed direction, and even moves are always the only other legal move
Moving the same disk twice in a row	You waste a move	If you catch yourself doing it, undo it, since an optimal solution never does this
Forgetting the goal peg is just another peg	You think a disk shouldn't leave it	Disks sit on the goal peg and leave again in the middle of the solution, which is normal
Counting moves wrong	Your count for n disks isn't 2^n − 1	That means you took a detour somewhere, so look back over your moves

Frequently Asked Questions

What is the minimum number of moves to solve the Tower of Hanoi?

For n disks with three pegs, the minimum is 2 to the power n, minus 1. That's 1 move for one disk, 3 for two, 7 for three, 15 for four, 31 for five and 63 for six. The reason is that the largest disk can only move when all the smaller disks are stacked on the third peg, which takes the minimum for n minus 1 disks, and then they have to be moved back on top of it. That gives the rule h(n) = 2 times h(n minus 1) plus 1, which works out to 2 to the n, minus 1.

How do you solve the Tower of Hanoi with 3 disks?

Label the pegs A (start), B (spare) and C (goal), and number the disks 1 (smallest) to 3. The seven moves are: disk 1 from A to C, disk 2 from A to B, disk 1 from C to B, disk 3 from A to C, disk 1 from B to A, disk 2 from B to C, and disk 1 from A to C. The first three moves park the two small disks on B, the fourth moves the big disk to the goal, and the last three bring the small disks back on top of it.

What is the easiest way to remember the solution?

Alternate two kinds of moves. On every odd-numbered move, shift the smallest disk one step around a circle: A to C to B and back to A if you have an odd number of disks, or A to B to C and back to A if you have an even number. On every even-numbered move, make the only legal move that doesn't touch the smallest disk. There's always exactly one. Following those two rules produces the shortest possible solution for any number of disks, with no planning needed.

How long would 64 disks take?

Moving 64 disks takes 18,446,744,073,709,551,615 moves, which is 2 to the 64th power minus 1. At one move per second without a break, that's about 584.5 billion years, using a year of 365.25 days. Edouard Lucas, who invented the puzzle, put it as more than five billion centuries. He also attached a legend about priests in a temple at Benares moving 64 gold disks, with the world ending when they finish. The math shows there's no need to worry about that deadline anytime soon.

Who invented the Tower of Hanoi?

The French mathematician Edouard Lucas invented it in 1883. He presented it under a playful pen name, Professor N. Claus de Siam of the Li-Sou-Stian college. Those names are anagrams: N. Claus de Siam uses the letters of Lucas d'Amiens, and Li-Sou-Stian uses the letters of Saint Louis. Lucas wrote about the puzzle and its temple legend in the third volume of his Recreations mathematiques. The puzzle is also called the Tower of Brahma, after the legend he told about it.

Why is the Tower of Hanoi used to teach recursion?

Because the cleanest solution is recursive: to move n disks, you move n minus 1 disks out of the way, move the biggest disk, then move the n minus 1 disks back on top. The smaller steps are the same puzzle with fewer disks, so the method calls itself until it reaches a single disk. That makes it a short, visual example of how a recursive program breaks a big problem into smaller copies of itself. It also shows why recursion can be expensive, since the work doubles with each extra disk.

Can the Tower of Hanoi be solved with four pegs?

Yes, and it's much faster. With four pegs, the minimum moves for 1 to 8 disks are 1, 3, 5, 9, 13, 17, 25 and 33, compared with 1, 3, 7, 15, 31, 63, 127 and 255 for three pegs. The usual method is the Frame-Stewart algorithm, which parks a group of top disks using all four pegs, moves the rest with three, and then brings the group back. Thierry Bousch proved this method optimal for four pegs in 2014. For five or more pegs, it's still an open question.

Is the Tower of Hanoi used in psychology tests?

Yes. Researchers use it to study planning and problem-solving because good play requires setting subgoals and sometimes moving disks away from the goal temporarily. In a 1995 study, Goel and Grafman found that adults with damage to the prefrontal cortex did significantly worse on the puzzle, and argued that the main difficulty was resolving conflicts between goals and subgoals. These are research and clinical tools used by trained professionals, so a home game isn't a test of anything. It's just a satisfying puzzle.

How does binary relate to the Tower of Hanoi?

Number the moves 1, 2, 3 and so on, and write each number in binary. Count the zeros at the right-hand end and add 1: that tells you which disk moves. Move 4 is 100 in binary, with two zeros, so it moves disk 3. This gives the pattern 1, 2, 1, 3, 1, 2, 1 for three disks. The same pattern shows up in the Gray code, a way of listing binary numbers where each step changes just one digit. The digit that changes at each step matches the disk that moves.

Can you ever solve the Tower of Hanoi in fewer than 2^n - 1 moves?

Not with three pegs and the standard rules. The largest disk has to move at least once, and when it does, every smaller disk must already be stacked on the third peg, since the big disk can't have anything on top of it or land on anything smaller. Building that stack takes at least the minimum for one fewer disk, and rebuilding it on top of the big disk takes that many again. Adding the one move for the big disk gives exactly 2^n - 1, so no shortcut exists. Extra pegs are a different story.

Sources

We checked every source below while writing this guide. Last reviewed October 30, 2026, by Joan Ramos.

1. Tower of Hanoi (Wolfram MathWorld)
2. Gray Code (Wolfram MathWorld)
3. Recreations mathematiques, Volume 3 (Edouard Lucas, Gauthier-Villars, 1893) (Internet Archive (digitized from Harvard University))
4. Are the frontal lobes implicated in planning functions? Interpreting data from the Tower of Hanoi (Goel and Grafman, Neuropsychologia, 1995) (PubMed, National Library of Medicine)
5. Specific impairments of planning (Shallice, Philosophical Transactions of the Royal Society B, 1982) (PubMed, National Library of Medicine)