Java Program to solve Towers of Hanoi puzzle using Recursion

One of the powerful example for solving a problem using recursion is Towers of Hanoi puzzle. This tutorial covers about what is Towers of Hanoi puzzle and how to solve the puzzle using recursion.

What is Tower of Hanoi puzzle? . We have three poles (or towers or rods), where the first pole has stack of different size disks. Let us label the first pole as ‘pole1’ , Second pole as ‘pole2’ and third pole as ‘pole3’

We have to move all the disks from the first pole (pole1) to the third pole (pole3) with the following conditions

1. At a time one disk can be moved

2. Big disk can not be placed on top of smaller disks

3. The second pole (pole2) is used as the temporary pole to hold disks

The above difficult problems can be easily solved by the technique Divide and conquer which divides the difficult problem into sub-problems recursively and finally the solution to all sub-problems is merged into a single solution of the difficult problem. Let us solve the above problem using recursion.

Let us assume that initially pole1 has n number of disks. disks are numbered 1 to n where disk 1 is smallest disk and disk n is the biggest disk. To move n disks from pole1 to pole3 , break the problems into sub problems as given below.


move n−1 disks from pole1 to pole2. // repeatedly called using recursion
move  1 disk (i.e. disk n)  from pole1 to pole3 // call move method
move n−1 disks from pole2 to pole3 // repeatedly called using recursion

The code to solve the problem using recursion is as follows.


package com.javaonline;

class HanoiTowers
{
public static void main(String args[]) {
HanoiTowers(4,"pole1" ,"pole3","pole2"); //totoal 3 disks ( disk 1 - smallest , disk 2 , disk 3 - biggest). pole2 is the temporary pole
}

private static void HanoiTowers( int n, String source ,String dest, String temp) // moving source                                                                                                       to destination using temporary
{
if (n == 1) move(n, source, dest );
else {
HanoiTowers( n-1, source,temp,dest ); //moves n-1 disks from pole1 to pole2 .
move( n, source, dest ); // moves disk number n from pole1 to pole3 , here n is the                                                                  top disk number in the source
HanoiTowers( n-1, temp , dest,source ); //moves n-1 disks from pole2 to pole3
}
}

private static void move (int diskNo, String source , String dest)
{
System.out.println("disk " + diskNo + " moves from top of " + source + " to top of " +dest );
}

}

Output :

towers of hanoi output
In the above program , instead of calling move method , you can directly call print statement. I have used move method for better understanding of the program.

Now let us calculate how many moves are required to move n disks from source to destination. The biggest disk is required the least number of moves (i.e. 1) and the smallest disk is required most number of moves. For example , if a pole have 4 disks (disk 1 , disk 2 , disk 3, disk 4) , then the disk 4 is moved one time only, disk 3 is moved 2 times , disk 2 is moved 4 times , disk 1 is moved 8 times. Total of 15 moves are required. So The number of moves required to solve a Tower of Hanoi puzzle is 2^n -1, where n is the number of disks

You may also like

Leave a Reply