Tower of Hanoi is a mathematical puzzle game which contains three rods and N number of disks each incrementally different diameters.
Initial condition: Initially all disks placed on one rod one above the other in stack manner (largest one is at the bottom and this follows…)
Goal: Move all disks from this rod (say rod1) to rod2 by taking help of rod3. (Note: For understanding purpose rod numbers are given. You can give rod numbers in any manner)
Rules to move disks from one rod to another rod:
Rule 1: At a time only one disk has to be moved.
Rule 2: Every time we have to choose only top disk from any rod to move.
Rule 3: While moving disk from one rod to other, at any time, always small size disk must place on larger size disk. In other way, a disk never be placed on other disk which is less size than it.
This is how a tower of Hanoi look like:
Below is the implementation of the tower of hanoi in java using recursion.
Java Tower of Hanoi Program
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public class toh{ static int count = 0; static void recursive_toh(int N, char from, char to, char using){ if (N == 1) { // base condition. If only one disk is there we can directly move it to target System.out.println ("Removing Disk 1 from rod"+ from +" and placing on rod" +to); count = count+1; return; } // see code explanation part for clear understanding of these 3 lins recursive_toh( N-1, from, using, to); System.out.println ("Removing Disk "+N+" from rod"+ from +" and placing on rod" +to); count = count+1; recursive_toh( N-1, using, to, from); } public static void main(String[] args) { int N = 4; //Number of disks recursive_toh(N,'1','3','2'); // Meaning of this line is // Move N disks from rod 1 to rod 3 using rod 2 System.out.println("Minimum No of disk movements for "+N+" disks is "+count); } } |
Output
Removing Disk 1 from rod1 and placing on rod2
Removing Disk 2 from rod1 and placing on rod3
Removing Disk 1 from rod2 and placing on rod3
Removing Disk 3 from rod1 and placing on rod2
Removing Disk 1 from rod3 and placing on rod1
Removing Disk 2 from rod3 and placing on rod2
Removing Disk 1 from rod1 and placing on rod2
Removing Disk 4 from rod1 and placing on rod3
Removing Disk 1 from rod2 and placing on rod3
Removing Disk 2 from rod2 and placing on rod1
Removing Disk 1 from rod3 and placing on rod1
Removing Disk 3 from rod2 and placing on rod3
Removing Disk 1 from rod1 and placing on rod2
Removing Disk 2 from rod1 and placing on rod3
Removing Disk 1 from rod2 and placing on rod3
Minimum No of disk movements for 4 disks is 15
Code Explanation
Here number of disks N=4. And goal looks like, rec_toh(N, ‘initial rod’, ‘final rod’, ‘helping rod’). i.e. We have to move N disks from initial rod to final rod using other one.
Base condition: When there is only one disk, we can directly move that one to target. Because tower of Hanoi with one disk never violates the rules.
Now there are N disks on rod1. We have to shift them to rod3 in same order means the largest one must be at bottom on rod3 also. But there are N-1 disks on top of it. For this what we have to do is, first move these top N-1 disks to aside (here to rod2). If you observe carefully this is leading to other tower of Hanoi problem of N-1 disks. Here our initial rod is same rod1. But target rod is rod2 since only one rod left we have to use rod3 as helping rod temporarily. So recursive form is rec_toh(N-1,from,using,to);
After moving all N-1 disks to rod2 from rod1 using rod3, now we can freely move Nth disk from rod1 to rod3 (target). That is the next line System.out.println();
Now we have to take back those N-1 disks from rod2 to rod3. So we have to use rod1. For this recursive from is rec_toh( N-1, using, to, from);
We can print the minimum number of disk movements required to move N disks. By giving count whenever we moved a disk. That is equal to 2N-1
Comment below if you have any queries related to tower of hanoi program in java.
