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 2^{N}-1

Comment below if you have any queries related to tower of hanoi program in java.