🗼 Tower of Hanoi
Recursive solver & 2ⁿ−1 moves
Move 0 / 7
Optimal: 7 moves
Mode
Setup
Controls
Stats
Moves
0
Optimal 2ⁿ−1
7
Recursion depth
0
Status
Ready
Move list
Info & Theory

The Tower of Hanoi asks you to move a stack of n disks from a source peg to a target peg, one disk at a time, never placing a larger disk on a smaller one.

The recursive idea

To move n disks from A to C using spare peg B:

  • Move the top n−1 disks from A to B (recursively).
  • Move the largest disk from A to C.
  • Move the n−1 disks from B to C (recursively).

Why 2ⁿ−1 moves

The move count satisfies T(n) = 2·T(n−1) + 1 with T(0) = 0. Unrolling the recurrence gives the closed form T(n) = 2ⁿ − 1. This is the proven minimum — no shorter solution exists.

Binary & Gray-code connection

Number the moves 1, 2, 3, … in binary. On move k the disk being moved is the position of the lowest set bit of k (disk 1 = smallest). The sequence of disk states traces a Gray code: each move flips exactly one disk, so consecutive states differ in one "digit", just like reflected binary Gray code.

The legend

In the temple legend, priests move 64 golden disks; the world ends when they finish. At one move per second that takes 2⁶⁴ − 1 ≈ 5.85 × 10¹¹ years — far longer than the age of the universe.

More pegs (Frame–Stewart)

With 4 or more pegs the optimal count drops sharply. The Frame–Stewart algorithm splits the stack and is conjectured optimal, but this simulation keeps the classic 3-peg core where 2ⁿ − 1 is exact.

About Tower of Hanoi

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 5 July 2026

The Tower of Hanoi is a mathematical puzzle invented by French mathematician Édouard Lucas in 1883. The task is to move a stack of N disks from a source peg to a destination peg using a third auxiliary peg, obeying the rule that no larger disk may be placed on a smaller one. The optimal recursive solution achieves this in exactly 2N − 1 moves, which is provably minimal: each sub-tower of N−1 disks must be moved twice (once off and once back onto the largest disk) plus one move for the bottom disk. For N=64 disks — the legendary premise of the puzzle — the minimum moves exceed 1.8 × 1019, requiring billions of years at one move per second.

This simulation animates the recursive solution for 1–8 disks, drawing each move step by step with configurable speed. A recursion call tree is displayed alongside the pegs, making the divide-and-conquer structure visible: each call to Hanoi(N) spawns Hanoi(N−1) twice, illuminating the exponential growth of the move count.

Frequently Asked Questions

Why does the Tower of Hanoi require exactly 2N − 1 moves?

By induction: for N=1, one move suffices (21−1=1). For N disks, we must first move the top N−1 disks to the auxiliary peg (2N−1−1 moves), then move the largest disk to the destination (1 move), then move the N−1 disk stack onto the destination (2N−1−1 moves). Total: 2·(2N−1−1)+1 = 2N−1. A lower-bound argument shows no solution can do fewer moves.

What is the iterative algorithm for Tower of Hanoi?

An elegant iterative algorithm alternates two rules: (1) make the legal move involving the smallest disk, and (2) make the unique legal move not involving the smallest disk. A binary interpretation also works: the disk moved on step m is the disk at the position of the lowest set bit of m. This connects Tower of Hanoi directly to binary counting and Gray code enumeration.

How does Tower of Hanoi illustrate recursion and divide-and-conquer?

The three-line recursive solution perfectly exemplifies divide and conquer: decompose the N-disk problem into two sub-problems of size N−1 and one base case (move one disk). The call tree is a complete binary tree of depth N with 2N−1 leaf calls (one per move), making the total work exactly 2N−1. This is the canonical example used in nearly every introductory algorithms textbook.

Is there a closed-form formula for which peg disk k is on after m moves?

Yes. Disk k (0-indexed, smallest) is on peg (bit k of m) XOR (bit k+1 of m) in a standard three-peg encoding, where m is expressed in binary. This allows O(log m) computation of any state without simulating all prior moves — a useful property for verifying large Hanoi sequences computationally or implementing fast state lookups.

What is the Frame-Stewart conjecture for four or more pegs?

With four pegs, fewer than 2N−1 moves may suffice. The Frame-Stewart algorithm (1941) conjectures the optimal move count is roughly 2·√(2N) for large N — exponentially better than the three-peg case. The conjecture was proved for four pegs by Bousch in 2014. For five or more pegs, the optimal count remains an open problem in combinatorics.

How long would it take to solve the 64-disk Tower of Hanoi?

The minimum moves for 64 disks is 264−1 ≈ 1.84 × 1019. At one move per second, this would take about 585 billion years — roughly 42 times the current age of the universe. Lucas referenced this in 1883, suggesting (humorously) that monks completing the puzzle would end the world.

How is Tower of Hanoi related to binary counting and the ruler sequence?

The sequence of disk numbers moved in the optimal solution is 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, … — known as the ruler sequence or Stern-Brocot ruler. The disk moved on step m equals the largest power of 2 dividing m (the position of the lowest set bit). This sequence is isomorphic to the sequence of bit positions that change when binary counting from 0 to 2N−1.

Can Tower of Hanoi be solved non-recursively with an explicit stack?

Yes. Push tuples (n, source, target, auxiliary) onto a stack. Pop a tuple: if n=1, emit a move; otherwise push three smaller tuples in reverse order. This eliminates function-call overhead and produces the same sequence. However, it still uses O(2N) stack entries to store all pending sub-problems, so space complexity is identical to the recursive approach.

How is the Hanoi graph related to the Sierpinski triangle?

The Hanoi graph — with valid disk configurations as vertices and legal single-disk moves as edges — is isomorphic to the Sierpinski triangle fractal at level N. The 3N states of an N-disk Hanoi problem form a self-similar graph where three copies of the N−1 problem are connected at corner vertices. This connection underpins applications in fractal analysis and graph-theoretic complexity studies.

Is Tower of Hanoi used in neuropsychological testing?

Yes. The Tower of Hanoi (and its close relative, the Tower of London) are standard tasks in neuropsychological assessment to evaluate executive function, working memory, and planning ability. Studies show patients with frontal lobe damage or Parkinson's disease perform significantly worse on multi-disk Hanoi tasks, making it a sensitive probe of prefrontal cortex function in clinical research.