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.
C++ Implementation
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)
C++ Implementation
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