Tower of Hanoi

What is the Tower of Hanoi puzzle?

The Tower of Hanoi is a puzzle with three pegs and a stack of discs of different sizes, and the task is to move the whole stack to another peg following two rules. At the start the discs sit on the first peg, the largest at the bottom and the smallest on top, like a cone. The rules are

1. move one disc at a time, the top disc of a peg; and
2. never put a larger disc on a smaller one.

The goal is the same tower on a different peg. With 3 discs it takes 7 moves. Call the pegs A, B and C, and the discs 1 (smallest), 2 and 3, moving from A to C:

Look at the table: the biggest disc moves once, in the middle, and the smallest disc moves at every other move. Both facts will turn out to be general.

Positions. Because a peg holds its discs in order of size, a position is completely described by saying which peg each disc is on. Any choice is legal, so with n discs there are exactly 3^n positions: 27 for three discs, 243 for five.

Play it below with three to seven discs. Click a peg (or use the buttons) to take the top disc, then click the peg to put it on. The hint button always makes the best next move from whatever position you are in.

How does the recursive solution work?

To move n discs from A to C, first move the top n-1 discs to B, then move the largest disc to C, then move the n-1 discs from B onto C. The largest disc cannot move until everything above it is out of the way, and it can only go to a peg that is empty or holds larger discs, which means a peg with no smaller disc on it. So all the other n-1 discs have to be on the third peg at that moment. That is the whole idea, and the two moves of the n-1 discs are the same puzzle again, with a smaller tower and with the pegs playing different roles:

• move n-1 discs from the source to the spare peg, using the target as the spare;
• move the largest disc from the source to the target;
• move n-1 discs from the spare peg to the target, using the source as the spare.

The recursion stops at 0 discs, where there is nothing to do. For three discs the recipe expands into the seven moves of the table: move 2 discs A→ B (three moves: 1 to C, 2 to B, 1 onto B), move disc 3 to C, move 2 discs B→ C (three more).

Counting the moves. Let T(n) be the number of moves of this solution. The two sub-solutions take T(n-1) each and the largest disc one move, so T(0)=0, T(n)=2 T(n-1)+1. Add 1 to both sides: T(n)+1=2 (T(n-1)+1), so T(n)+1 doubles at every step, starting from T(0)+1=1. Hence T(n)+1=2^n, T(n)=2^n-1. Check: T(1)=1, T(2)=3, T(3)=7, T(4)=15, T(5)=31, T(10)=1023. Another way to see it: disc number k (the smallest is 1) moves 2^n-k times, and 1+2+4+…+2^n-1=2^n-1 is a geometric series.

What the computer does. The function calls itself twice, so it makes 2^n+1-1 calls in all, but the depth of the recursion is only n: at any time the call stack holds one call for each size from n down to the current one. So a program can solve 25 discs (33 million moves) without running out of stack, though it will take its time. This is unlike the naive recursion for Fibonacci numbers, which can be rescued by remembering values: here the answer itself contains 2^n-1 moves, so no program can be faster than that.

Why can no solution use fewer moves?

The recursive solution is not just good, it is the best possible: no solution has fewer than 2^n-1 moves, and no other solution has exactly that many. The proof uses the largest disc, as the construction did. Let M(n) be the least number of moves of any legal solution with n discs.

Look at a solution and at the largest disc. It must move at least once. At the moment of its first move, it goes from the first peg to another peg, and for that to be allowed every other disc must be on the third peg. So before that moment the n-1 smaller discs have been moved from the first peg to the third one, which is the same puzzle with n-1 discs, and takes at least M(n-1) moves. After the last move of the largest disc it sits on the target peg, and the n-1 smaller discs, which are on another peg, still have to be moved onto it: at least M(n-1) moves again. Adding the largest disc's own move, M(n)\ge2 M(n-1)+1, M(1)=1. So M(n)\ge2^n-1, which the recursive solution reaches. The best solution has exactly 2^n-1 moves.

It is unique. If a solution has exactly 2^n-1 moves, every inequality above must be an equality: the largest disc moves exactly once (otherwise there would be an extra move), and the moves before and after it are each a shortest solution for n-1 discs. By induction on n there is only one such solution: the recursive one. A shortest solution needs no choice at all, which also explains why the hint button in the puzzle never has to pick between two best moves.

From any position. The same idea solves the puzzle from any position, not only from a full tower. Find the largest disc that is not yet where it should be; move the smaller discs to the third peg, move that disc, and rebuild a perfect tower on top of it. The number of moves is smallest possible, and the largest distance between any two positions of n discs is 2^n-1, between two of the three "corner" positions with everything on one peg.

How long would the 64-disc tower take?

Far longer than the universe has existed: at one move a second, 2^64-1 moves take about 5.85×10^11 years. In the story Lucas's leaflet told in 1883, and a French science magazine retold in 1884, monks in a temple at Benares are moving 64 golden discs between three diamond needles, one move at a time, and when they finish the world will end. The number of moves is 2^64-1=18 446 744 073 709 551 615. At one move a second that is 585 billion years, about 42 times the age of the universe (13.8 billion years). The doubling is what hurts: every extra disc doubles the time. At one move a second 10 discs take 17 minutes, 20 discs 12 days, 30 discs 34 years and 40 discs 34 800 years. Even a computer that makes a billion moves a second would need 585 years for 64 discs.

This is the standard picture of exponential growth (see Big-O notation for the growth classes): adding one disc multiplies the work by 2, whereas for a polynomial cost like n^2 it would add a little. It is also why the legend is only a legend. Move the slider below to see the time for any number of discs, and how often each disc moves.

How is the Tower of Hanoi connected to binary numbers?

The disc that moves at move number m is read off the binary form of m: it is the position of the lowest 1 bit. Number the moves 1,2,3,…,2^n-1 and the discs 1 (smallest) to n. Then move m moves disc v+1, where 2^v is the largest power of two that divides m (the number of zeros at the right end of m in binary). The sequence of discs is the ruler sequence 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,… Odd moves (m ends in 1) move disc 1; moves 2,6,10,… move disc 2; move 8 moves disc 4; move 2^n-1 moves the largest disc n, once, in the middle. The count of moves of each disc, 2^n-k for disc k, is the count of numbers up to 2^n-1 with exactly k-1 trailing zeros.

A solution without recursion. Because of that, the solution can be run as a loop:

1. On odd moves, move the smallest disc one peg onward, always in the same direction around the three pegs: A→ C→ B→ A→… if n is odd, A→ B→ C→ A→… if n is even.
2. On even moves, make the only legal move that does not involve the smallest disc.

This makes exactly the same moves as the recursion. It also lets a program write down the move number m of a 64-disc tower in a few steps, without making the m-1 moves before it.

The position after m moves. The recursion can be unrolled once per disc, from the largest down. If m is below 2^n-1 the largest disc has not moved yet, and the smaller discs are on their way to the spare peg; otherwise it is on the target, 2^n-1 is taken off m, and the smaller discs are on their way to the target from the spare peg. The result gives the peg of each of the n discs after any number of moves in n steps, as the widget below does for up to 64 discs.

Gray code. Write each m as its reflected binary Gray code m⊕\lfloor m/2\rfloor (the exclusive or of m with itself shifted right). Consecutive Gray codes differ in exactly one bit, and the bit that changes at move m is bit number v, the same ruler sequence. So bit k of the Gray code of m is 1 when disc k+1 has moved an odd number of times so far. Frank Gray used the same code in a patent for telegraph signals (filed in 1947); Gray codes are used for position sensors, where only one bit may change at a time.

Type any move number below, or step through the moves.

What does the graph of all positions look like?

Draw every position as a dot and join two dots by a line when one move turns one position into the other, and you get a Sierpiński triangle. For one disc the graph is a triangle: the disc can be on A, B or C, and it can move between any two pegs. For n discs, split the positions by the peg of the largest disc: three groups, each a copy of the graph for n-1 discs (with the large disc fixed, the smaller ones move as before). The three copies are joined by only three lines, one for each move of the largest disc, which can happen only when all smaller discs are on the third peg. Repeating this gives the triangle of triangles of triangles.

The graph has these properties, which the widget lets you check by eye: - 3^n points, all the positions; - (3^n+1-3)/(2) lines, since every position allows three moves except the three corner positions, where all discs are on one peg and only the top disc can move, to either of two pegs: 39 lines for 3 discs; - three corners: all discs on A, on B or on C; - the best solution is a path along one side of the big triangle, from the top corner to the bottom right one, with 2^n-1 steps, and it is the only shortest path between those corners: the number of moves cannot be shortened because there is nothing shorter to take; - the distance between two positions is the length of a shortest path, and the largest distance in the graph is 2^n-1.

This explains the self-similarity of the recursion. It also links the puzzle to the Sierpiński triangle and to Pascal's triangle taken mod 2, as the same pattern in different disguises. Choose the number of discs below and click any dot to see the position and its distance from a finished tower on each peg.

What if there are four or more pegs?

With a fourth peg the puzzle becomes much easier, and the best number of moves is given by a recurrence of Frame and Stewart that was proved optimal for four pegs only in 2014. The idea: move the top k discs to a spare peg using all four pegs, then move the remaining n-k discs to the target using only three pegs (one is occupied by the k small discs), then move the k discs onto the target, using all four pegs again. If F(n,p) is the number of moves with p pegs, F(n,3)=2^n-1, F(n,p)=\min_1\le k<n\Bigl(2 F(k,p)+F(n-k,p-1)\Bigr). For four pegs this gives 1,3,5,9,13,17,25,33,41,49,… for n=1,2,3,…: the differences are 2,2,4,4,4,8,8,8,8,…, each power of two repeated one more time than the last. Compare three pegs: 1,3,7,15,31,…. For ten discs it is 49 moves instead of 1023, and for 20 discs 289 instead of 1 048 575.

The saving grows fast. For 64 discs, four pegs need 18 433 moves, five pegs 1535 and six pegs 673, against 18 446 744 073 709 551 615 for three pegs: at one move a second the four-peg tower takes about 5 hours, and the five-peg tower about 26 minutes.

What is known. Henry Dudeney published a four-peg version, "Reve's puzzle", in 1907. In 1941 J. S. Frame and B. M. Stewart gave the recurrence above, independently. Whether it is optimal was an open problem for more than seventy years: Thierry Bousch proved it for four pegs in 2014. For five or more pegs the Frame–Stewart numbers are only conjectured to be best (a search over all positions confirms them for small cases). Pick the number of pegs and discs below.

How do you solve the Tower of Hanoi in Python, JavaScript and C++?

The recursive function is five lines in any language: solve n-1, move the largest disc, solve n-1 again, with the roles of the pegs rotated. The Python program below returns the list of moves, checks that the loop version makes exactly the same moves, finds the disc of move m from the lowest set bit, and computes the position after m moves of a tower of 64 discs without making them. The JavaScript and C++ programs repeat the recursion and the ruler sequence.

def hanoi(n, source="A", target="C", spare="B", moves=None):
    """Moves (disc, from, to) of the best solution; disc 1 is the smallest."""
    if moves is None:
        moves = []
    if n == 0:
        return moves
    hanoi(n - 1, source, spare, target, moves)      # clear the n - 1 smaller discs onto the spare peg
    moves.append((n, source, target))               # the largest disc goes straight to its place
    hanoi(n - 1, spare, target, source, moves)      # and the smaller discs are rebuilt on top of it
    return moves


def hanoi_iterative(n):
    """The same moves without recursion: the smallest disc always goes round the pegs the same way."""
    pegs = {"A": list(range(n, 0, -1)), "B": [], "C": []}
    cycle = ["A", "C", "B"] if n % 2 else ["A", "B", "C"]
    where, moves = 0, []
    for step in range(1, 2 ** n):
        if step % 2:                                 # odd moves: the smallest disc
            src, dst = cycle[where], cycle[(where + 1) % 3]
            where = (where + 1) % 3
        else:                                        # even moves: the only legal move of the other two pegs
            a, b = [p for p in "ABC" if p != cycle[where]]
            if not pegs[a] or (pegs[b] and pegs[b][-1] < pegs[a][-1]):
                a, b = b, a
            src, dst = a, b
        disc = pegs[src].pop()
        pegs[dst].append(disc)
        moves.append((disc, src, dst))
    return moves


def disc_at_move(m):
    """Which disc moves at move m (1, 2, 3, ...): the position of the lowest 1 bit of m."""
    return (m & -m).bit_length()


def position_after(n, m):
    """The peg of each disc after m moves, computed from the bits of m without making the moves."""
    source, target, spare = "A", "C", "B"
    where = {}
    for k in range(n, 0, -1):
        half = 2 ** (k - 1)
        if m < half:
            where[k] = source
            target, spare = spare, target
        else:
            where[k] = target
            m -= half
            source, spare = spare, source
    return where


print(hanoi(3))
print(len(hanoi(10)), hanoi_iterative(10) == hanoi(10), 2 ** 10 - 1)
print([disc_at_move(m) for m in range(1, 16)])
print(position_after(5, 15), position_after(5, 16))
print(2 ** 64 - 1, round((2 ** 64 - 1) / (365.25 * 24 * 3600) / 1e9), "billion years at one move a second")
print(position_after(64, 10 ** 18)[64], position_after(64, 10 ** 18)[1])
# [(1, 'A', 'C'), (2, 'A', 'B'), (1, 'C', 'B'), (3, 'A', 'C'), (1, 'B', 'A'), (2, 'B', 'C'), (1, 'A', 'C')]
# 1023 True 1023
# [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]
# {5: 'A', 4: 'B', 3: 'B', 2: 'B', 1: 'B'} {5: 'C', 4: 'B', 3: 'B', 2: 'B', 1: 'B'}
# 18446744073709551615 585 billion years at one move a second
# A C

const hanoi = (n, from = 'A', to = 'C', via = 'B', moves = []) => {
  if (n === 0) return moves
  hanoi(n - 1, from, via, to, moves)
  moves.push([n, from, to])
  hanoi(n - 1, via, to, from, moves)
  return moves
}
hanoi(3).map(([d, a, b]) => d + ':' + a + b).join(' ')   // '1:AC 2:AB 1:CB 3:AC 1:BA 2:BC 1:AC'
hanoi(10).length                                           // 1023

// the disc of move m is the position of the lowest set bit: m & -m keeps only that bit
const disc = (m) => Math.log2(m & -m) + 1
Array.from({ length: 15 }, (_, i) => disc(i + 1))          // [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]

2n ** 64n - 1n                                             // 18446744073709551615n: BigInt, since a double would round it
Number(2n ** 64n - 1n) / 1e9 / (365.25 * 24 * 3600)        // 584.54...: years at a billion moves a second

// the stack only holds n calls at a time, although 2^n - 1 moves are made
let count = 0
const go = (n) => { if (n === 0) return; go(n - 1); count++; go(n - 1) }
go(20)
count                                                      // 1048575

#include <iostream>
#include <cstdio>
using namespace std;

int moves = 0;
int show = 1;

void hanoi(int n, char from, char to, char via) {
  if (n == 0) return;
  hanoi(n - 1, from, via, to);
  moves++;
  if (show) printf("disc %d: %c -> %c\n", n, from, to);
  hanoi(n - 1, via, to, from);
}

int main() {
  hanoi(3, 'A', 'C', 'B');

  show = 0;
  moves = 0;
  hanoi(12, 'A', 'C', 'B');
  printf("%d\n", moves);                                // 2^12 - 1

  for (int m = 1; m <= 15; m++) {                       // the disc of move m: trailing zeros of m, plus one
    int d = 1, x = m;
    while (x % 2 == 0) {
      x = x / 2;
      d++;
    }
    printf("%d%c", d, m == 15 ? '\n' : ',');
  }
  return 0;
}

/* output:
disc 1: A -> C
disc 2: A -> B
disc 1: C -> B
disc 3: A -> C
disc 1: B -> A
disc 2: B -> C
disc 1: A -> C
4095
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
*/

Where does the Tower of Hanoi come from?

The Tower of Hanoi is a French invention of 1883, wrapped in a legend that is itself part of the invention.

• 1883. The mathematician Édouard Lucas put the puzzle on sale as La Tour d'Hanoï, véritable casse-tête annamite ("the Tower of Hanoi, a true Vietnamese brain-teaser"), with eight discs, under the invented name N. Claus (de Siam), mandarin of the Li-Sou-Stian college. The names are anagrams: N. Claus de Siam is Lucas d'Amiens (he came from Amiens) and Li-Sou-Stian is Saint-Louis, the school where he taught. The leaflet carried the legend of the temple in Benares and the end of the world.
• 1884. Henri de Parville retold the story in the magazine La Nature and helped it spread; W. W. Rouse Ball's Mathematical Recreations and Essays carried it into English.
• 1907. Henry Dudeney published a four-peg version, "Reve's puzzle", in The Canterbury Puzzles.
• 1939–1941. A problem in the American Mathematical Monthly about four pegs led J. S. Frame and B. M. Stewart to the recurrence that bears their names.
• 1950s. The Gray code of Frank Gray (patented in 1953) turned out to describe the sequence of discs.
• 1970s. Psychologists, among them Herbert Simon, used the puzzle to study how people plan and solve problems; versions of it are used in tests of planning ability.
• 1989–1990s. Andreas Hinz and others studied the graph of positions and its relation to the Sierpiński triangle, and the average distance between positions.
• 2014. Thierry Bousch proved that the Frame–Stewart numbers are optimal for four pegs.

What mistakes do people make with the Tower of Hanoi?

The most common mistakes with the Tower of Hanoi are the nine below, each with the correct statement.

Practice: test your understanding

These questions mix everything above. A wrong answer costs nothing here: read the hint and try again.

Summary: the Tower of Hanoi at a glance

• Rules: three pegs, one disc at a time, never a larger disc on a smaller one; 3^n positions.
• Recursion: solve n-1 onto the spare peg, move the largest, solve n-1 onto it; T(n)=2T(n-1)+1, so T(n)=2^n-1.
• Optimal and unique: the largest disc must move, with all others on the third peg before and the same work again after: M(n)\ge2M(n-1)+1.
• Time: 64 discs, 2^64-1 moves, 585 billion years at one move a second; the recursion is n deep.
• Binary: move m moves disc v+1 for the lowest set bit 2^v of m; disc k moves 2^n-k times; the loop version moves the smallest disc the same way around every other move; Gray code.
• Graph: the 3^n positions form a Sierpiński triangle, and the best solution is one side of it.
• More pegs: Frame–Stewart F(n,p)=\min(2F(k,p)+F(n-k,p-1)), optimal for p=4 (2014): 64 discs in 18 433 moves.
• History: Lucas 1883, Dudeney 1907, Frame and Stewart 1941, Bousch 2014.

Glossary: key terms

Tower of Hanoi

A puzzle of moving a stack of discs between three pegs, one disc at a time, never putting a larger disc on a smaller one.

Recursion

A method of solving a problem by solving smaller copies of the same problem and combining the results.

Recurrence relation of moves

The equation T(n) = 2T(n−1) + 1 for the number of moves of the best solution with n discs.

Exponential growth

Growth in which each extra unit of input multiplies the cost by a constant, as each extra disc doubles the number of moves.

Ruler sequence

The sequence 1, 2, 1, 3, 1, 2, 1, 4, … in which the term at position m is one plus the number of trailing zeros of m in binary.

Gray code

A binary numbering in which consecutive numbers differ in exactly one bit.

Sierpiński triangle

A fractal made of three half-size copies of itself placed at the corners of a triangle; the graph of positions of the Tower of Hanoi has this shape.

Frame–Stewart numbers

The number of moves of the best known solutions of the Tower of Hanoi with four or more pegs, found by splitting the tower at the best place.

Frequently asked questions

References

1. Andreas M. Hinz, Sandi Klavžar, Ciril Petr (2018). The Tower of Hanoi – Myths and Maths (2nd ed.). Birkhäuser.
2. Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1994). Concrete Mathematics (2nd ed.), section 1.1: The Tower of Hanoi. Addison-Wesley.
3. N. Claus (de Siam) [Édouard Lucas] (1883). La Tour d'Hanoï, véritable casse-tête annamite. Paris, Paul Bousrez.
4. Thierry Bousch (2014). La quatrième tour de Hanoï. Bulletin of the Belgian Mathematical Society – Simon Stevin 21.
5. J. S. Frame and B. M. Stewart (1941). Solution to Advanced Problem 3918. The American Mathematical Monthly 48.
6. Henry E. Dudeney (1907). The Canterbury Puzzles. Heinemann, London.

Related articles

• Big-O Notation: Big-O notation explained: the definition, growth rates from O(1) to O(n!), counting steps in code, best and worst case, recurrences and the Master theorem.
• Binary Numbers: How Computers Count, Convert and Calculate: Binary numbers explained: bits and place value, converting to decimal and hex, binary arithmetic, two’s complement, bitwise operators and binary fractions.
• Geometric Sequences and Series: Ratio, Sums and Growth: Geometric sequences and series explained: common ratio, the n-th term, finite and infinite sums, geometric means, compound interest and decay, with practice.
• Fibonacci Numbers: Fibonacci numbers explained: the recurrence, Binet's formula, identities, fast doubling, Zeckendorf sums, Pisano periods and the golden ratio, with code.