Tower of Hanoi

Hi Coder, Tower of Hanoi is a Classical Question where we have three towers and n disks, where n is a positive number.

The disks are increasingly placed in terms of size such that the smallest disk is on top and the largest disk is on the bottom.

The objective of the Problem is to print instructions to move the disk from one to another tower, obeying the following simple rules:

● move 1 disk at a time.

● never place a smaller disk under a larger disk.

● you can only move a disk at the top.

Before coming to the solution we have can divide the problem into two parts

High-Level Thinking and Low-Level Thinking.

According to High-Level Thinking is Expectation of toh() function is moving 3 discs from A to B using C tower While obeying the above rules.

Let’s Establish the faith — Low-Level Thinking

toh(2,A,B,C) While obeying the above rules should print instructions

to move the disk from one to another tower.

Now Faith→ Expectation meet means toh(3,A,B,C) can be achieved from toh(2,A,B,C).

If toh() function knows How to print the Instructions to move 2 disks (while obeying the three rules) then we can make toh() function to print the instructions to move 3 disks.

Let us now introduce the general process

TOWER(N, BEG, AUX, END) to denote a procedure that moves the top disks from the initial BEG to the final END using the AUX When n = 1, we have the following obvious solution: TOWER(1, BEG, AUX, END) consists of the single instruction BEG→ END Furthermore, when is 1, the solution may be reduced to the solution of the following three subproblems:

(1) TOWER(N -1, BEG, END, AUX)

(2) T0WER( 1 , BEG, AUX, END) or BEG-END

(3) TOWER(N — 1, AUX, BEG, END)

Observe that each of these three subproblems may be solved directly or is essentially the same as the original problem using fewer disks. (using low-level thinking)

Pseudo-Code ( Tower of Hanoi -Recursive Approach)

#include <bits/stdc++.h>
using namespace std;
void towerOfHanoi(int n, char from_rod,char to_rod, char aux_rod){
//From_rod is Source
//to_rod is Destination
//aux_rod is helper rod
if (n == 0){return;}
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
cout<<"MoveTower ("<<n<<","<<from_rod<<","<<aux_rod<<","<<to_rod<<")"<<endl;
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}
int main(){
int n = 3; // Number of disks
towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
return 0;
}

OUTPUT :

MoveTower (1,A,B,C)
MoveTower (2,A,C,B)
MoveTower (1,C,A,B)
MoveTower (3,A,B,C)
MoveTower (1,B,C,A)
MoveTower (2,B,A,C)
MoveTower (1,A,B,C)

you can also build a Dry Run calls of above function for Calls to visualize what happens when recursion takes places

Also you can refer this Link