Tower of Hanoi

Tower of Hanoi

Rules

  1. Only one disc can be moved at a time
  2. Each move consist of taking the top disc of one of the stacks and placing it on top of another stack / rod.
  3. No larger disk may be placed on a smaller disc.

Recursive solution

def hanoi(n, 1, 3, 2) // Move n disks from rod 1 - 3 using rod 2
if n > 0
  hanoi(n - 1, 2, 3)
  move disk n from rod 1 -> rod 3
  hanoi(n - 1, 2, 3, 1)

Lower bounds

Let the lower bound be some \(S(n)\).

Consider two scenarios:

  • What happened before disk n (relative position from top of a stack) is moved to the last rod 3

    We have to move n - 1 discs on top of the nth disk first.

    T(n - 1)

  • What happened to move n disk on to rod 3

    We have to move n - 1 discs to the rod 3.

    T(n - 1)

Therefore we prove the minimum runtime,

T(0) = 0 T(n) = 2T(n - 1) + 1

logo