Tower of Hanoi - Step-by-Step Puzzle Solver & Visualizer

How to use this tool

1. Select the number of discs (1–8).
2. Press Play to auto-solve, or use Step to advance one move at a time.
3. Adjust speed with the slider.

The puzzle

The Tower of Hanoi consists of three pegs and a set of discs of decreasing size stacked on the leftmost peg. The goal is to move the entire stack to another peg following these rules:

• Move only one disc at a time.
• A disc may only be placed on top of a larger disc or on an empty peg.

Start:           Goal:
Peg A  B  C     Peg A  B  C
 [1]            |    |  [1]
 [2]            |    |  [2]
 [3]            |    |  [3]

The math

The minimum number of moves required to solve an n-disc Tower of Hanoi is 2ⁿ − 1.

The recursive solution

The elegant recursive algorithm: to move n discs from peg A to peg C using peg B as auxiliary:

1. Move n−1 discs from A to B.
2. Move disc n from A to C.
3. Move n−1 discs from B to C.

This recursion produces exactly 2ⁿ − 1 moves and is the foundation for understanding recursion in computer science.

The iterative solution

The Tower of Hanoi can also be solved iteratively (without recursion) using just two rules:

1. On odd moves: move the smallest disc one peg to the right (cyclically: A->B->C->A).
2. On even moves: make the only legal move that does not involve the smallest disc.

Repeating these two steps alternately solves the puzzle in 2ⁿ − 1 moves. This also corresponds to counting in binary: each disc maps to a bit position, and a disc moves when its corresponding bit changes in the binary count from 0 to 2ⁿ − 1.

Why this problem matters in computer science

The Tower of Hanoi is a canonical teaching example for several reasons:

• Recursion: the three-line recursive solution is one of the clearest demonstrations that a complex problem can be solved by defining it in terms of smaller instances of itself.
• Binary counting: the sequence of moves corresponds exactly to incrementing a binary number; peg A = bit 0, peg B = bit 1, peg C = bit 2. This surprising connection between a physical puzzle and number representation is a favorite teaching moment.
• Exponential complexity: the 2ⁿ − 1 move count demonstrates concretely why exponential-time algorithms quickly become impractical: 64 discs requires 18,446,744,073,709,551,615 moves.

Variations

• 4-peg (Reve's puzzle): adding a fourth peg reduces the minimum number of moves significantly. The Frame-Stewart conjecture proposes an optimal algorithm, but it has not been proven for all values of n - it remains an open problem in computer science.
• Restricted Hanoi: allow moves only between adjacent pegs (A↔B, B↔C but not A↔C directly). The minimum move count increases to 3ⁿ − 1.
• Bi-color Hanoi: discs have two colors and must be sorted by color as well as size.