Tower of Hanoi is a very old problem. People had been solving it for many years. In this problem, you have to shift disk from one peg to another peg using the third peg. Let me explain it more.

The set up of the problem is like in the above picture. There will be three pegs and every peg has its own name as the first peg is named “source” and the second peg is named “destination” and the third peg named as “via”. Now, these named suggest there work. You have to shift all the disks from source to destination using the via a peg. Now you might be thinking this is the easiest problem you have heard off, you can just pick all the disks and put it in the destination peg without using any third peg. But it’s not that simple because there is catch here, you can move one disk at a time and no larger disk can be above the smaller disk while performing shifting. Now the problem becomes a little tricky.

Many people had tried this problem with a different number of disks and some succeed and some not. Some take more number of moves to solve and some take less.

So, I have made this project on the tower of Hanoi in which first it takes the input of the number of disks and then it gives the output in which it displays the order in which the disks are being moved.

I have used the concept of Recursion in this project which is very important to solve the problem of the tower of Hanoi. I have made a method called tower which is a recursive method. In the parameters of this method I have provided the number of disks and source and destination and via a peg.

1 2 3 |
void tower(int n, char source, char des, char via); |

Inside this method, we have two cases one is base and other is the recursive case. In base case, we just print which ring is moving from which peg to which peg using some peg.

1 2 3 4 5 |
if(n == 1){ cout << "Moved the ring "<< n << " from " << source << " to " << des << " via " << via << ".\n"; } |

In recursive case we use the method two times and in between them we print the message again.

1 2 3 4 5 6 7 |
else{ tower(n-1,source, via, des); cout << "Moved the ring " << n << " from " << source << " to " << des << " via " << via << ".\n"; tower(n-1,via,des,source); } |

So now the recursive method is ready to use in the main method. In the main method, we assign the different pegs value and takes the input of the number of rings and then calling the tower method, which does all the work.

C++ Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> using namespace std; void tower(int n, char source, char des, char via){ if(n == 1){ cout << "Moved the ring "<< n << " from " << source << " to " << des << " via " << via << ".\n"; } else{ tower(n-1,source, via, des); cout << "Moved the ring " << n << " from " << source << " to " << des << " via " << via << ".\n"; tower(n-1,via,des,source); } } int main() { int rings; char source='A'; char des = 'B'; char via = 'C'; cout << "Enter the number of rings : "; cin >> rings; tower(rings,source,des,via); return 0; } |

Output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
Enter the number of rings : 5 Moved the ring 1 from A to B via C. Moved the ring 2 from A to C via B. Moved the ring 1 from B to C via A. Moved the ring 3 from A to B via C. Moved the ring 1 from C to A via B. Moved the ring 2 from C to B via A. Moved the ring 1 from A to B via C. Moved the ring 4 from A to C via B. Moved the ring 1 from B to C via A. Moved the ring 2 from B to A via C. Moved the ring 1 from C to A via B. Moved the ring 3 from B to C via A. Moved the ring 1 from A to B via C. Moved the ring 2 from A to C via B. Moved the ring 1 from B to C via A. Moved the ring 5 from A to B via C. Moved the ring 1 from C to A via B. Moved the ring 2 from C to B via A. Moved the ring 1 from A to B via C. Moved the ring 3 from C to A via B. Moved the ring 1 from B to C via A. Moved the ring 2 from B to A via C. Moved the ring 1 from C to A via B. Moved the ring 4 from C to B via A. Moved the ring 1 from A to B via C. Moved the ring 2 from A to C via B. Moved the ring 1 from B to C via A. Moved the ring 3 from A to B via C. Moved the ring 1 from C to A via B. Moved the ring 2 from C to B via A. Moved the ring 1 from A to B via C. |