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
Tagged on:

Leave a Reply

Your email address will not be published. Required fields are marked *

This website stores some user agent data. These data are used to provide a more personalized experience and to track your whereabouts around our website in compliance with the European General Data Protection Regulation. If you decide to opt-out of any future tracking, a cookie will be set up in your browser to remember this choice for one year. I Agree, Deny
504

By continuing to use the site, you agree to the use of cookies. You can read more about it the Cookies&Privacy Policy Section Above. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this. You can read more about it the Cookies&Privacy Policy Section.

Close