TOWERS OF HANOI

 Note - Recursive algorithm used

The Towers of Hanoi is one of the most famous classic problems in Computer Science that almost every Computer Scientist has to tackle with at least once in their entire lifetime.

LEGEND
According to legends, In the Far East, there exists a temple where few diligent priests are trying to move a stack of golden disks from one diamond peg to another. There are three pegs in total and the stack has 64 disks threaded onto one peg arranged in increasing order of size from top to bottom. The priests are moving the stack from one peg to another under the conditions that exactly one disk is moved at a time and never should a larger disk be placed over a smaller disk. And it is said that that the world will come to an end by the time the priests complete their task.

To learn more about Towers of Hanoi  CLICK HERE !!!

QUESTION
Write a C++ algorithm to move n number of disks from peg1 to peg2 under the given conditions :

• Only one disk is to be moved at a time.
• Each move consists of moving a disk from one peg to another.
• Never should a larger disk be placed over a smaller disk.

SOLUTION
Steps to be followed :

• All disks are to be moved from peg1 to peg2.
• Let n be the number of disks.
• Moving n disks can be viewed in terms of moving only n –1 disks (hence n-1 recursions).
• Move n – 1 disks from peg1 to peg3, using peg2 as a temporary holding area.
• Move the last disk (the largest) from peg1 to peg2
• Move the n – 1 disks from peg3 to peg2, using peg1 as a temporary holding area.
• The process ends when n equals 1 disk (i.e., the base case for our recursive algorithm). 

(Steps to be followed by the algorithm for n = 4)


Source Code

1. 
   
2. #include<iostream.h>
3. 
   
4. using namespace std;
5. 
   
6. void TOH(int,char,char,char);
7. 
   
8. int main()
9. {  
10.   int n =0;
11.   cout<<"\nEnter the number of discs to be used :";
12.   cin>>n;
13.   TOH(n,'A','B','C');
14.   return 0;
15. }
16. void TOH (int n ,char peg1 ,char peg2 ,char peg3)
17. {
18.   if(n==1)
19.    {
20.       cout<<"\n"<<peg1<<" --> "<<peg2;
21.    }
22.   else
23.    {
24.       TOH (n-1 , peg1 , peg3 , peg2);
25.       cout<<"\n"<<peg1<<" --> "<<peg2;
26.       TOH (n-1 , peg3 , peg2 , peg1);
27.    }
28. }
29. 
    

OUTPUT(for n =4)

A --> C

A --> B

C --> B

A --> C

B --> A

B --> C

A --> C

A --> B

C --> B

C --> A

B --> A

C --> B

A --> C

A --> B

C --> B

( If you like the content here, follow TSP on social media to get notified on future updates)