Tower of Hanoi

Play Tower of Hanoi online

The board at the top of this page is a free Tower of Hanoi game that runs in your browser — nothing to download, no account to make. Choose 3 to 15 disks, then move the whole stack from the left tower to the right one.

• Phone or tablet: tap a tower to lift its top disk, then tap another to drop it.
• Mouse: drag a disk across, or click one tower and then another.
• Keyboard: ← and → choose a tower, ↑ lifts and ↓ drops; 1, 2 and 3 go straight to towers A, B and C, and Esc puts the disk back.

Mistakes cost nothing. Undo takes back your last move, Reset starts the same size again, and Hint lifts the disk the shortest solution would move next and says where it goes. Step plays it for you. If you would rather watch, Auto Solve finishes the puzzle from wherever the board is, not only from the start.

Nothing is counted until you move. After your first move the panel shows:

• your moves, a timer and an efficiency score — your game as a percentage of a perfect one;
• whether you are still on the optimal path, or how many moves behind it you are.

The timeline under the board records the whole game. Scrub back to any earlier position, or replay it at 0.5×, 1×, 2× or 4×; the same speed setting paces Auto Solve. Focus Mode clears away everything but the towers, and the page remembers how many disks you last played. When you finish, the result screen compares your moves with the minimum and offers you one more disk.

The Tower of Hanoi problem

The Tower of Hanoi problem starts with three towers and a stack of disks of different sizes on one of them, largest at the bottom. The goal is to move the whole stack to another tower, under three rules:

1. Move one disk at a time.
2. Only the top disk of a tower can move.
3. A larger disk may never sit on a smaller one.

That is the whole puzzle, and it takes about a minute to learn. The third rule is what makes it hard: every disk has to wait somewhere legal while the disks beneath it move, and with only three towers there is never much room. How to play Tower of Hanoi has them in pictures, with a practice board and a worked example.

The French mathematician Édouard Lucas published the puzzle in 1883. A year later a magazine article presenting it added the legend it is famous for: Brahmin priests moving sixty-four golden disks, with the world to end when they finished. At one move a second, that would take roughly 585 billion years.

Tower of Hanoi minimum moves and the 2ⁿ − 1 formula

The minimum number of moves for a Tower of Hanoi with n disks is 2ⁿ − 1, often typed as 2^n − 1. Three disks take 7 moves, four take 15, and the Tower of Hanoi with 5 disks takes a minimum of 31 moves. That is a proven floor rather than a record: no shorter solution exists for any size, and it is the number the efficiency score on the board measures you against.

The equation behind the formula

The Tower of Hanoi equation comes straight from the rules. Before the largest disk can move, the n − 1 disks above it have to be stacked on the spare tower; then it crosses; then those disks come back on top of it. Writing T(n) for the fewest moves that does all of that:

T(n) = 2·T(n − 1) + 1, starting from T(0) = 0 — no disks, no moves.

Each size costs twice the size below it, plus one: 1, 3, 7, 15, 31, 63. Every one of those is one less than a power of two, which is where the closed form T(n) = 2ⁿ − 1 comes from. The proof that 2ⁿ − 1 is the minimum works through both halves of that claim — why that many moves is always enough, and why fewer is impossible — and the Tower of Hanoi minimum moves calculator gives the exact count for any number of disks up to sixty-four.

Minimum moves by number of disks

Each size links to its full solution, every move listed and played on a board. The largest game here is 15 disks, or 32,767 moves: every disk you add doubles the length of the game, plus one move.

The Tower of Hanoi algorithm and recursion

The equation above is also the algorithm, read as instructions. To move n disks from a source tower to a target tower:

1. Move n − 1 disks from the source to the spare tower.
2. Move the largest disk from the source to the target.
3. Move the n − 1 disks from the spare tower onto the target.

Steps 1 and 3 are the same problem with one disk fewer, so the algorithm solves them by calling itself, and a call with no disks left to move simply returns. That is Tower of Hanoi recursion in full, and it is why nearly every computer science course uses this puzzle to teach recursion. The trick is not to picture every move at once: trust the smaller call to do its job, and the three steps are the whole solution.

Because the algorithm makes exactly 2ⁿ − 1 moves, its running time is O(2ⁿ), and nothing can beat that: every one of those moves has to be made. Its memory use is only O(n). The Tower of Hanoi algorithm page runs the code line by line beside a live board and draws the tree of calls as it goes, and the iterative solution produces the same moves from two rules and a loop.

Tower of Hanoi in Python, Java and other languages

The three steps translate almost word for word into code. Tower of Hanoi in Python is a seven-line function: a base case for zero disks, two recursive calls, and the one line between them that prints a move. Tower of Hanoi in Java is the same method inside a class, and the place to find out why the count for sixty-four disks does not fit in a long. There are complete programs in JavaScript, C, C++ and C# as well.

Every listing has been run and its output checked against the solver on this site, and each comes with a walkthrough that explains why every line is there rather than what the syntax is.

More ways to play and learn

Once three towers and a full stack feel easy, there is more to try:

• The daily challenge — one scrambled position, the same for everyone, new at midnight UTC. Solve it without the solver to keep a streak going.
• The Tower of Hanoi solver — every move of the shortest solution from any legal position, including the one you are stuck in on this board.
• Strategies — the one repeating idea behind every size, and a rule that tells you the next move without planning ahead.
• Variants — four towers instead of three, a ring where disks travel one way, two colours to sort, and a random starting position.
• For teachers — a 45-minute lesson plan, a printable worksheet with answers, and a board to embed in a course page.

Frequently asked questions