Home » Algorithm » Datastructure » Interviews » Miscellaneous » Tower Of Hanoi Program in Java.

Tower Of Hanoi Program in Java.

in , , , - on 22:00:00 - No comments

Tower Of Hanoi Java Program

Lets see Tower of Hanoi program in Java. We will use Recursive algorithm to solve Tower of Hanoi problem. Towers of  Hanoi is a basically a famous game in which you are given a 3 Pegs, Start peg, Auxiliary or Helper peg and End Peg.

Start peg contains 3 disks of different sizes as shown. You have to move all the disk from Start peg to End peg using Auxiliary peg.  

There are few rules that need to keep in mind,
1. Only one disk can be moved at a time.
2. Large size disk can't be placed on top of small sized disk.

Lets understand what is the input and the expected output.


Algorithm

Say if there is,

Only 1 disk present (n=1)


We can directly move 1 disk from Peg A (Source) to Peg B (Destination).

Note: There is no use of Auxiliary peg when there is only 1 disk, So we directly moved it from source to destination.

So, for total 1 disk, irrespective of the Peg it is present, moving it to any other Peg requires 
only 1 step.
(1 disk can be moved from Peg A to Peg B, Peg B to Peg C, Peg C to Peg A  etc. in 1 step.)
In our recursion, this will be our base case.
When the disk remaining is only 1, then directly move it from Start to End.
2 disk present (n=2)

For 2 disks, we need to perform below 3 steps,
1. Move disk 1 from peg A to peg Help,
2. Move disk 2 from peg A to peg B,
3. Move disk 1 from peg Help to peg B.
 

So this say, for moving 2 disk from Peg A to Peg B, it requires 3 steps.
Note: In general we can say, for 2 disks, it requires minimum 3 Steps to move disks from any source peg to any destination peg.

 3 disk present (n=3)

If we have 3 disk, we will first break down it into 2 disk (and further narrow it down to 1 disk) using recursion.
We already know how to solve problem with 2 disk.

In our Towers of Hanoi problem, If there is more then 2 disk, then recurse on the disk until only one disk is remaining.

That is, we will write a recursive function that takes below parameter,
1. Disk that need to be moved.
2. Source Peg from where the disk need to be moved,
3. Auxiliary Peg which will be helper peg for performing operation.
4. Destination Peg to which the disk should be moved,

Let's see how it works in case of 3 disks.

Can we make 3 disk tower to 2 disk tower logically
(2 disk tower because we already know how to solve 2 disk tower.)

Yes, by considering 3rd(last) disk as 1 unit and above 2 disk (Disk 1 and Disk 2) as 1 unit,
So now it became 2 disk tower.

We already know how to move tower containing 2 disk.

Wait!!!.. How can we move 2 disk all together in one go... We are violating rule here.
So what we will do is further narrow down that 2 disk sub tower to 1 disk sub tower.

For narrowing down, we will use recursion in which 3rd disk will be in memory and first play with only top 2 disk and move that from Source Peg to Auxiliary Peg.

Now at top only 1 disk is remaining and we already know how to solve it.
This steps we are performing to remove nth(last) disk as that is the largest disk and need to be moved to Destination Peg.

We moved top 2 disk from Source to Auxiliary Peg and now the Pegs will look like below,


While backtracking, we are left with only 1 disk in Peg A, So directly move it from source peg to destination peg.

Now, all disks from Peg Help need to be moved to Peg B.

We will follow same procedure that we used to move them from Peg A to Peg Help but this time Source will be Peg Help and destination will be Peg B.
So, If you have n disk, it can be moved from any peg to any other peg recursively.
Note: When n==1, it means only 1 disk is left and just moved the disk directly from source to destination peg because there is only one disk and no point of smaller or larger disk.
In all the other cases, we will execute 3 steps recursive procedure.

So to summarize it, To move n discs from Source Peg to Destination Peg:
1. Move n−1 discs from Source Peg to Auxiliary Peg. This leaves nth disc alone on Source peg.
2. Move nth disc from Source Peg to Destination Peg.
3. Move n−1 discs from Auxiliary Peg to Destination Peg, so they sit on nth disc.

How recursive solution is working in solving Tower of Hanoi puzzle?

Consider there are N disks in Source Peg that need to be moved to Destination peg.

To move all the disk to the destination peg, we first need to move the bottom-most disk from Source peg to the destination peg first because that is the largest disk and will be at bottom of destination peg. 

For doing this, first we need to move the N-1 disks above the bottom most disk to Auxiliary/Helper peg first. 

Moving N-1 disks to Helper Peg is same as solving the Tower of Hanoi Problem with N-1 disks.  So this is the recursive task and therefore we can write a recursive algorithm. 

How much minimum steps are required to move all disk from Source peg to Destination Peg?

We saw that for 1 disk tower, we required total 1 step to move disk from Source to Destination peg.For 2 disk tower, we require 3 steps.
For n disk tower, how much steps are required?

Tower of disk (1) = Total 1 steps.
Tower of disk (2) = Total 3 steps. 
Tower of disk (3) = Total 7 steps. 
Tower of disk (4) = Total 15 steps.
Tower of disk (5) = Total 31 steps. 
Tower of disk (6) = Total 63 steps.
Tower of disk (n) = 2^n - 1

Tower of Hanoi Program in Java.

package javabypatel;

public class TowersOfHanoi {

 public void moveDisks(int n, String start, String auxiliary, String end) {
  if (n == 1) {

   // When n==1, it means we are left with only one disk, so directly move it from source to destination.
   System.out.println(start + " -> " + end); 

  } else {

   // Move (n-1 disk) from Source Peg to Auxiliary Peg
   moveDisks(n - 1, start, end, auxiliary);    

   //Move last nth disk to Destination Peg.
   System.out.println(start + " -> " + end);  

   //Move (n-1 disk) from Auxiliary Peg to Destination Peg.
   moveDisks(n - 1, auxiliary, start, end); 
  }
 }

 public static void main(String[] args) {
  TowersOfHanoi towersOfHanoi = new TowersOfHanoi();  
  towersOfHanoi.moveDisks(3, "source peg", "helper peg", "destination peg");
 }
}

Full Stack trace of Program.

Recursive Tree Structure.


Categories: , , ,

Post a Comment