At the time of formation of the world, Brahma made a precious stone tower with 64 discs made of gold in it. The disks were of decreasing size and were stacked on the tower in an order (the biggest will be at the base and the following littler in size will be over the keep going etc).
Other than this tower there were two other towers. Since the creation, Brahman ministers have been endeavoring to move the circles from tower A to tower C utilizing tower B for middle stockpiling.As the disks are very heavy, they can be moved only one at a time.
Likewise, at no time can a bigger plate be on top of a littler circle. As indicated by Brahma, the world will reach an end when the ministers have finished their errand.
The most captivating thing about this riddle is the legend can be demonstrated deductively genuine. On the off chance that the ministers had the capacity to move circles at a rate of one for each second, utilizing the littlest number of moves, it would take them (2^64)-1 seconds (same no. of moves) or about 585 billion years to complete, which is around 127 times the present age of the sun.
Java Program for Tower of Hanoi Problem
Before we dissect the project, I would like to give few attributes with respect to the calculated model of the towers. I’ve picked utilizing a non-recursive model as it would be somewhat easy to clarify and get it.
We have three towers named t1, t2, and t3.They are represented utilizing Arrays such that the first element of every tower is zero. On the off chance that the tower is unfilled it will be comprising of all 0’s.
You can look at the image to grab a better perspective of the towers.
I declared a class for it that exposes methods to swap discs between the towers, print the status of each tower and to initialize the towers.
First is the initialization of towers which will be accomplished by the parameterized constructor as shown below. The starting tower consists of all the discs in order hence it is a separate case.
Tower(int disc,boolean initial){
seq= new int[disc+1];
if(initial){
discCount=disc;
for(int i=1;i<=discCount;i++){
seq[i]=disc;
disc--;
}
top=seq[discCount];
}
else {
discCount=0;
top=0;
}
}
The next part is just swapping all the discs until we transfer all the discs from tower 1 to tower 3.
This will be done by the following if else loop.
int x=0;
if((input%2)==1){
while(t3.discCount!=input){
t1.swap(t3);
System.out.println("nSwap between Tower 1 and 3");
x++;
if(t3.discCount!=input){
t1.swap(t2);
System.out.println("Swap between Tower 1 and 2");
x++;
}
if(t3.discCount!=input) {
t2.swap(t3);
System.out.println("Swap between Tower 2 and 3");
x++;
}
System.out.println("nStatus:");
System.out.println("Tower1:t"); t1.print();
System.out.println("Tower2:t"); t2.print();
System.out.println("Tower3:t"); t3.print();
}
}
else{
while(t3.discCount!=input){
t1.swap(t2);
System.out.println("nSwap between Tower 1 and 2");
x++;
if(t3.discCount!=input) {
t1.swap(t3);
System.out.println("Swap between Tower 1 and 3");
x++;
}
if(t3.discCount!=input) {
t2.swap(t3);
System.out.println("Swap between Tower 2 and 3");
x++;
}
System.out.println("nStatus:");
System.out.println("Tower1:t"); t1.print();
System.out.println("Tower2:t"); t2.print();
System.out.println("Tower3:t"); t3.print();
}
}
Actually if you have observed I’ve used a sequence here for even and odd number of discs.
Algorithm for Swapping Discs
The perfect algorithm for moving the towers is given below.
For an even number of discs
1. Make the move of disc between t1 and t2.
2. Make the move of disc between t1 and t3.
3. Make the move of disc between t2 and t3.
4. Repeat until complete.
For an odd number of discs
1. Make the move of disc between t1 and t3.
2. Make the move of disc between t1 and t2.
3. Make the move of disc between t3 and t2.
4. Repeat until complete.
The final program is given below.
import java.util.Scanner;
class Tower{
int discCount;
int seq[];
int top;
Tower(int disc,boolean initial){
seq= new int[disc+1];
if(initial){
discCount=disc;
for(int i=1;i<=discCount;i++){
seq[i]=disc;
disc--;
}
top=seq[discCount];
}
else {
discCount=0;
top=0;
}
}
void print(){
for(int i=0;i<=discCount;i++){
System.out.print(seq[i]+" ");
}
System.out.println("top="+top);
}
void swap(Tower temp){
if(this.top!=0&&temp.top!=0){
if(this.top<temp.top){
temp.discCount++;
temp.seq[temp.discCount]=this.top;
this.seq[this.discCount]=0;
this.discCount--;
}
else{
this.discCount++;
this.seq[this.discCount]=temp.top;
temp.seq[temp.discCount]=0;
temp.discCount--;
}
}
if(temp.top==0&&this.top!=0){
temp.discCount++;
temp.seq[temp.discCount]=this.top;
this.seq[this.discCount]=0;
this.discCount--;
}
if(temp.top!=0&&this.top==0){
this.discCount++;
this.seq[this.discCount]=temp.top;
temp.seq[temp.discCount]=0;
temp.discCount--;
}
if(discCount!=0)
top=seq[discCount];
else
top=0;
if(temp.discCount!=0)
temp.top=temp.seq[temp.discCount];
else
temp.top=0;
}
}
class Towers_brahma{
public static void main(String args[]){
int input;
//get the no. of discs from user
System.out.println("Enter the no. of discs");
Scanner in= new Scanner(System.in);
input=in.nextInt();
in.close();
Tower t1= new Tower(input,true);
Tower t2= new Tower(input,false);
Tower t3= new Tower(input,false);
//starting swapping the discs, every iteration swaps one disc from each tower
int x=0;
if((input%2)==1){
while(t3.discCount!=input){
t1.swap(t3);
System.out.println("nSwap between Tower 1 and 3");
x++;
if(t3.discCount!=input){
t1.swap(t2);
System.out.println("Swap between Tower 1 and 2");
x++;
}
if(t3.discCount!=input) {
t2.swap(t3);
System.out.println("Swap between Tower 2 and 3");
x++;
}
System.out.println("nStatus:");
System.out.println("Tower1:t"); t1.print();
System.out.println("Tower2:t"); t2.print();
System.out.println("Tower3:t"); t3.print();
}
}
else{
while(t3.discCount!=input){
t1.swap(t2);
System.out.println("nSwap between Tower 1 and 2");
x++;
if(t3.discCount!=input) {
t1.swap(t3);
System.out.println("Swap between Tower 1 and 3");
x++;
}
if(t3.discCount!=input) {
t2.swap(t3);
System.out.println("Swap between Tower 2 and 3");
x++;
}
System.out.println("nStatus:");
System.out.println("Tower1:t"); t1.print();
System.out.println("Tower2:t"); t2.print();
System.out.println("Tower3:t"); t3.print();
}
}
System.out.println("nNo. of swappings="+x);
}
}
Sample Output
