# Tower of Hanoi

### Rules

- Only one disc can be moved at a time
- Each move consist of taking the
*top*disc of one of the stacks and placing it on top of another stack / rod. - 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 3We 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