inthink.guide
ShopBack to home

Play. Predict. Understand.

Tower of Hanoi

Play with 3–5 disks, ask for a hint from your current board, and learn the recursive strategy through two short animations. Open a step-by-step example whenever you need it.

Play Tower of Hanoi
ABCDisk 44Disk 33Disk 22Disk 11

Free the largest disk by moving the smaller stack out of its way.

Tower of Hanoi rules

  1. Move the entire stack from column A to column C.
  2. Move only one disk at a time, taking the top disk from a column.
  3. Never place a larger disk on top of a smaller one.

Play Tower of Hanoi

Choose a source column, then a destination. The disk numbers show size: 1 is the smallest. Undo a move or reset to try a new approach.

0 moves
ABCDisk 33Disk 22Disk 11

Select a source column, then a destination.

Hints follow your current board. They never move a disk for you; a legal detour can still be solved.

How to solve Tower of Hanoi

Think about the largest disk first. In this four-disk example, three smaller disks stand in its way. Solve that smaller problem before moving disk 4.

  1. Move the smaller stack aside

    Move disks 1, 2 and 3 from A to B, using C as the spare column. Keep disk 4 on A. Now C is clear and disk 4 is exposed.

    ABCDisk 44Disk 33Disk 22Disk 11

  2. Move the largest disk

    Move disk 4 from A to C. That single move puts the largest disk in its final position.

    ABCDisk 44Disk 33Disk 22Disk 11

  3. Bring the smaller stack back

    Move disks 1, 2 and 3 from B to C, using A as the spare column. They fit on disk 4, and the puzzle is solved.

    ABCDisk 44Disk 33Disk 22Disk 11

Each smaller stack uses the same three-part plan: move all but its largest disk aside, move that disk, then bring the smaller stack onto it. Stop when only one disk remains: move it directly. This is recursion; the source, destination and spare column change with each smaller problem.

Learn by predicting the next goal

These separate four-disk examples leave your practice board untouched. Pause, step through a move, answer a prediction or reveal the explanation.

1. Clear a path for the largest disk

Watch three smaller disks make room for disk 4. Predict where they must be before the largest disk can move.

Separate four-disk example

Goal: move 3 disks from A to B, using C as the spare column.

ABCDisk 44Disk 33Disk 22Disk 11

First clear a path: move the top three disks from A to B.

Step 0 of 8

2. Repeat the smaller problem

Disk 4 is already on C. The remaining job is the same puzzle with three disks and different column roles.

Separate four-disk example

Goal: move 3 disks from B to C, using A as the spare column.

ABCDisk 44Disk 33Disk 22Disk 11

Disk 4 stays on C. Now solve the three-disk problem from B to C.

To move three disks from B to C using A, where should disk 1 go first?

Step 0 of 7

Step-by-step solutions

These examples start with every disk on A and finish on C. Open any example directly; your practice board stays as it is.

Minimum number of moves

T(n) = 2T(n − 1) + 1 = 2ⁿ − 1

A standard solution moves the smaller stack twice and the largest disk once. That gives T(n) = 2T(n − 1) + 1. A single disk takes one move, so the minimum for n disks is 2ⁿ − 1.

3 disks: 7 moves. 4 disks: 15 moves. 5 disks: 31 moves.

3 disks — 7 moves

Starting position: all disks on A; destination: C. Disk 1 is the smallest.

  1. Move disk 1 from A to C.
  2. Move disk 2 from A to B.
  3. Move disk 1 from C to B.
  4. Move disk 3 from A to C.
  5. Move disk 1 from B to A.
  6. Move disk 2 from B to C.
  7. Move disk 1 from A to C.
4 disks — 15 moves

Starting position: all disks on A; destination: C. Disk 1 is the smallest.

  1. Move disk 1 from A to B.
  2. Move disk 2 from A to C.
  3. Move disk 1 from B to C.
  4. Move disk 3 from A to B.
  5. Move disk 1 from C to A.
  6. Move disk 2 from C to B.
  7. Move disk 1 from A to B.
  8. Move disk 4 from A to C.
  9. Move disk 1 from B to C.
  10. Move disk 2 from B to A.
  11. Move disk 1 from C to A.
  12. Move disk 3 from B to C.
  13. Move disk 1 from A to B.
  14. Move disk 2 from A to C.
  15. Move disk 1 from B to C.
5 disks — 31 moves

Starting position: all disks on A; destination: C. Disk 1 is the smallest.

  1. Move disk 1 from A to C.
  2. Move disk 2 from A to B.
  3. Move disk 1 from C to B.
  4. Move disk 3 from A to C.
  5. Move disk 1 from B to A.
  6. Move disk 2 from B to C.
  7. Move disk 1 from A to C.
  8. Move disk 4 from A to B.
  9. Move disk 1 from C to B.
  10. Move disk 2 from C to A.
  11. Move disk 1 from B to A.
  12. Move disk 3 from C to B.
  13. Move disk 1 from A to C.
  14. Move disk 2 from A to B.
  15. Move disk 1 from C to B.
  16. Move disk 5 from A to C.
  17. Move disk 1 from B to A.
  18. Move disk 2 from B to C.
  19. Move disk 1 from A to C.
  20. Move disk 3 from B to A.
  21. Move disk 1 from C to B.
  22. Move disk 2 from C to A.
  23. Move disk 1 from B to A.
  24. Move disk 4 from B to C.
  25. Move disk 1 from A to C.
  26. Move disk 2 from A to B.
  27. Move disk 1 from C to B.
  28. Move disk 3 from A to C.
  29. Move disk 1 from B to A.
  30. Move disk 2 from B to C.
  31. Move disk 1 from A to C.

What if my board differs from the example?

Any position that follows the size rule can still reach C. A repeated position is a loop, not a dead end. The formula above applies to the standard start; it is not the remaining move count for an arbitrary board. Use a hint to find a next move from your actual position.

Puzzles →