The objective of the Tower of Hanoi puzzle is to move all discs from one tower to another one. The rules applied to the puzzle:
– Player can move one disc at the time.
– Only top discs from towers can be placed.
– Disks can be only placed on bigger ones.

The amount of moves needed to solve this puzzle can be calculated from equation:

amountOfMoves = pow(2, n) – 1.

For 3 discs it takes 7 moves, for 4 discs 15 moves, …

### Iterative algorithm:

```IN: 3 Towers: A B C, Tower A with n discs sorted from top to bottom in ascending order, Tower B and C are empty.
OUT: All discs placed on tower B or C.
1. Move smallest disc to the next tower(from 0 to 1, from 1 to 2, from 2 to 0). If all discs are on one tower end algorithm.
2. Make the only possible move of disc, which is not the smallest disc. Return to step 1.```

### Recursive algorithm:

```IN: 3 Towers: A B C, n.
OUT: All discs placed on tower B or C.
1. If n = 0, end algorithm.
2a. Apply this algorithm for (n - 1, A, C, B)
2b. Move last disc from tower A to B.
2c. Apply this algorithm for (n - 1, C, B, A)```

### Algorithm Output for 4 discs:

```0. Moved disc 1 from tower 0 to tower 1
1. Moved disc 2 from tower 0 to tower 2
2. Moved disc 1 from tower 1 to tower 2
3. Moved disc 3 from tower 0 to tower 1
4. Moved disc 1 from tower 2 to tower 0
5. Moved disc 2 from tower 2 to tower 1
6. Moved disc 1 from tower 0 to tower 1
7. Moved disc 4 from tower 0 to tower 2
8. Moved disc 1 from tower 1 to tower 2
9. Moved disc 2 from tower 1 to tower 0
10. Moved disc 1 from tower 2 to tower 0
11. Moved disc 3 from tower 1 to tower 2
12. Moved disc 1 from tower 0 to tower 1
13. Moved disc 2 from tower 0 to tower 2
14. Moved disc 1 from tower 1 to tower 2```

### Algorithm visualisation for 4 discs:

Hanoi Tower Solver Algorithm
Tagged on: