Implementation of **Tower of HANOI in using C++ program**, Learn: What is **Tower of Hanoi**? How to implement using recursion in C++?

Submitted by Abhishek Jain, on July 23, 2017

The **Tower of Hanoi** is a mathematical puzzle invented by the French mathematician Edouard Lucas in 1883.

There are three pegs, source(A), Auxiliary (B) and Destination(C). Peg A contains a set of disks stacked to resemble a tower, with the largest disk at the bottom and the smallest disk at the top. **figure 1** Illustrate the initial configuration of the pegs for 3 disks. The objective is to transfer the entire tower of disks in peg A to peg C maintaining the same order of the disks.

**Obeying the following rules:**

- Only one disk can be transfer at a time.
- Each move consists of taking the upper disk from one of the peg and placing it on the top of another peg i.e. a disk can only be moved if it is the uppermost disk of the peg.
- Never a larger disk is placed on a smaller disk during the transfer.

**(figure 1)**

The solution to the puzzle calls for an application of recursive functions and recurrence relations.

A skeletal recursive procedure (Outline) for the solution of the problem for N number of disks is as follows:

- Move the top N-1 disks from peg A to peg B (using C as an auxiliarypeg)
- Move the bottom disk from peg A to peg C
- Move N-1 disks from Peg B to Peg C (using Peg A as an auxiliary peg)

The pictorial representation of the skeletal recursive procedure for N=4 disks is shown in **Figure 2**.

**(figure 2)**

TOH( n, Sour, Aux , Des)If(n=1) Write ("Move Disk “, n ," from ", Sour ," to ",Des) ElseTOH(n-1,Sour,Des,Aux);Write ("Move Disk “, n ," from ", Sour ," to ",Des)TOH(n-1,Aux,Sour,Des);END

**Let’s take an example to better understand the algorithm (For n=3).**

**(figure 3)**

#include<iostream> using namespace std; //tower of HANOI function implementation void TOH(int n,char Sour, char Aux,char Des) { if(n==1) { cout<<"Move Disk "<<n<<" from "<<Sour<<" to "<<Des<<endl; return; } TOH(n-1,Sour,Des,Aux); cout<<"Move Disk "<<n<<" from "<<Sour<<" to "<<Des<<endl; TOH(n-1,Aux,Sour,Des); } //main program int main() { int n; cout<<"Enter no. of disks:"; cin>>n; //calling the TOH TOH(n,'A','B','C'); return 0; }

Output

Enter no. of disks:3 Move Disk 1 from A to C Move Disk 2 from A to B Move Disk 1 from C to B Move Disk 3 from A to C Move Disk 1 from B to A Move Disk 2 from B to C Move Disk 1 from A to C

**Image Reference:**

- http://www.peterloos.de/index.php/m-wpf/m-wpf-userdefined-controls/59-a-wpf-towersofhanoi
- http://algorithms.tutorialhorizon.com/towers-of-hanoi/
- https://www.researchgate.net/publication/278658550_An_Evolutionary_Approach_to_Tower_of_Hanoi_Problem

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions

.resCodeAS1 { display: block; width: 320px; height: 50px; }
@media(min-width: 300px) { .resCodeAS1 { display: none; } }
@media(min-width: 480px) { .resCodeAS1 { display: none; } }
@media(min-width: 750px) { .resCodeAS1 { display: block; width: 336px; height: 280px; } }
(adsbygoogle = window.adsbygoogle || []).push({});

(adsbygoogle = window.adsbygoogle || []).push({});

(adsbygoogle = window.adsbygoogle || []).push({});

solved programs: » C » C++ » DS » Java » C# |

aptitude que. & ans.: » C » C++ » Java » DBMS |

interview que. & ans.: » C » Embedded C » Java » SEO » HR |

close Like other websites, this site uses cookies to deliver relevant ads based on your interest, by using our website, you acknowledge that you have read our privacy policy.