Skip to main content

Solve TOH for 3 disks

Short answer

For 3 disks (1 smallest, 3 largest) from A to C using B: move 1 A→C, 2 A→B, 1 C→B, 3 A→C, 1 B→A, 2 B→C, 1 A→C. This follows the recursive pattern: top 2 to B, largest to C, then 2 to C. Total moves 7.

Explain the TOH problem and show the steps to solve it using recursion for 3 disks.

Problem

Three pegs A (source), B (auxiliary), C (destination); n disks on A, smallest on top. Move all to C, one disk at a time, only the top disk of a peg, and never a larger disk on a smaller one.

Recursive idea

TOH(n, from, to, aux): (1) TOH(n-1, from, aux, to); (2) move disk n from from to to; (3) TOH(n-1, aux, to, from). For n = 1 just move the disk.

Steps for 3 disks (1 smallest, 3 largest)

TOH(3,A,C,B) = TOH(2,A,B,C), move 3: A→C, TOH(2,B,C,A)

  • TOH(2,A,B,C) = TOH(1,A,C,B) [1: A→C], 2: A→B, TOH(1,C,B,A) [3: C→B]
  • TOH(2,B,C,A) = TOH(1,B,A,C) [5: B→A], 6: B→C, TOH(1,A,C,B) [7: A→C]
MoveDiskFromToPegs after the move (A / B / C)
11AC3,2 / - / 1
22AB3 / 2 / 1
31CB3 / 2,1 / -
43AC- / 2,1 / 3
51BA1 / 2 / 3
62BC1 / - / 3,2
71AC- / - / 3,2,1
Start   : A: 3 2 1 | B: - | C: -
Move 4  : A: -     | B: 2 1 | C: 3     (largest disk placed)
Finish  : A: -     | B: -   | C: 3 2 1

Total moves = 2³ − 1 = 7.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 5 questions →