Tower Of Hanoi
Lets understand what is the input and the expected output.
So the question is, You have given a 3 Peg (Start peg, Auxiliary/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.
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.2 disk present (n=2)
When the disk remaining is only 1, then directly move it from Start to End.
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.miscellaneous;
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.
You may also like to see
Given an array of integers. All numbers occur thrice except one number which occurs once. Find the number in O(n) time & constant extra space.
Count number of Bits to be flipped to convert A to B
Count number of Set Bits in Integer.
Check if number is Power of Two.
Find all subsets of a set (Power Set).
Skyline Problem in Java.
Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted
Count trailing zeros in factorial of a number
When to use SOAP over REST Web Service. Is REST better than SOAP?
Tower Of Hanoi Program in Java.
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment