Back Button
Back to Chapter
C++ Introduction
No items found.
C++ Basics
No items found.
C++ Control Statements
No items found.
C++ Logical Operators
No items found.
C++ Procedural Programming
No items found.
C++ Structural Programming
No items found.
C++ Implementation of OOPS
No items found.
C++ Arrays and Vectors
No items found.
C++ Error Handling
No items found.
C++ File Handling
No items found.
Collapse_Icon
Table of Contents

The tower of Hanoi is a famous problem in which we have three rods and n disks. The aim of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
  3. No bigger disk may be placed on top of a smaller disk.

Now let us discuss our approach to this problem

We have 3 discs as shown in the figure. Now in each step we only move 1 discs

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/1555803b-efce-4ab5-911f-0df7753e9446/Untitled_Diagram_(62).png

First step disc red →C

Second step disc blue →B

Third step disc red →B

Fourth step disc green →C

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/18fd4c34-4b00-43bd-9240-fdf6cc6d621e/Untitled_Diagram_(63).png

fifth step move red disc→A

sixth step move blue disc→C

seventh step move red disc →C

And we have successfully moved all discs to rod C

Based on your knowledge try to write a C++ program to solve this problem.

Hint: make use of recursion.

Solution:

#include using namespace std; void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) { if (n == 1) { cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod<
Output: Move disk 1 from rod X to rod Z Move disk 2 from rod X to rod Y Move disk 1 from rod Z to rod Y Move disk 3 from rod X to rod Z Move disk 1 from rod Y to rod X Move disk 2 from rod Y to rod Z Move disk 1 from rod X to rod Z Move disk 4 from rod X to rod Y Move disk 1 from rod Z to rod Y Move disk 2 from rod Z to rod X Move disk 1 from rod Y to rod X Move disk 3 from rod Z to rod Y Move disk 1 from rod X to rod Z Move disk 2 from rod X to rod Y Move disk 1 from rod Z to rod Y