Tower of Hanoi Problem using recursion in Java

In this Java tutorial, we are going to discuss the famous Tower of Hanoi problem using ‘n’ disks. We are going to solve it using recursive function calling approach.

What is in the Tower of Hanoi Problem?

The Tower of Hanoi is a Mathematical puzzle. It consists of three rods and ‘n’ disks of different sizes which can slide onto any rod. In the puzzle, there are three rods suppose, left one is source rod, middle one Auxiliary rod, and right one destination rod. Source rod consists of ‘n’ disks in descending order of their sizes considering from the bottom where the smallest disk is at the top. We have to move all disks from source rod to destination rod using auxiliary rod by following rules:-

  • We can not move more than one disk at a time
  • We are not allowed to place a larger disk on a smaller one

 

     Demonstration using 3 Disks

 Algorithm to solve tower of Hanoi problem in Java:-

  1. Move the top n-1 disks from source to Auxiliary rod.
  2. Move nth disk from source to destination rod.
  3. Move n-1 disks from Auxiliary to destination rod.

Java Code for solving Tower of Hanoi Problem using 3 Disks

 
  class Codespeedy
{ 
   
  static void result(long n, char source, char destination, char auxiliary) 
  { 
    if (n == 1) 
    { 
      System.out.println("Move disk 1 from " + source + " to " + destination); // print the task
      return; 
    } 
    
       result(n-1, source, auxiliary, destination); 
    
    System.out.println("Move disk " + n + " from " + source + " to " + destination); // print the task
    
         result(n-1, auxiliary, destination, source); 
  } 
  
  
  public static void main(String args[]) 
  { 
      long n = 3; // Number of disks 
       result(n,'A','C','B'); // A, B and C are names of rods 
  } 
} 

OUTPUT

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n − 1, where n is the number of disks.

You may also learn




 


Leave a Reply

Your email address will not be published. Required fields are marked *