Java Program to Solve Tower of Hanoi using Stacks

This is a Java Program to solve Tower of Hanoi Problem using stacks. Stack is an area of memory that holds all local variables and parameters used by any function and remembers the order in which functions are called so that function returns occur correctly. ‘push’ operation is used to add an element to stack and ‘pop’ operation is used to remove an element from stack. ‘peek’ operation is also implemented returning the value of the top element without removing it. The relation between the push and pop operations is such that the stack is a Last-In-First-Out (LIFO) data structure.

The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:
i) Only one disk may be moved at a time.
ii) Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
iii) No disk may be placed on top of a smaller disk.

Here is the source code of the Java program to solve Tower of Hanoi Problem using stacks. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /*
  2.  * Java Program to Solve Tower of Hanoi Problem using Stacks
  3.  */
  4.  
  5.  import java.util.*;
  6.  
  7.  /* Class TowerOfHanoiUsingStacks */
  8.  public class TowerOfHanoiUsingStacks
  9.  {
  10.      public static int N;
  11.      /* Creating Stack array  */
  12.      public static Stack<Integer>[] tower = new Stack[4]; 
  13.  
  14.      public static void main(String[] args)
  15.      {
  16.          Scanner scan = new Scanner(System.in);
  17.          tower[1] = new Stack<Integer>();
  18.          tower[2] = new Stack<Integer>();
  19.          tower[3] = new Stack<Integer>();
  20.          /* Accepting number of disks */         
  21.          System.out.println("Enter number of disks");
  22.          int num = scan.nextInt();
  23.          N = num;
  24.          toh(num);
  25.      }
  26.      /* Function to push disks into stack */
  27.      public static void toh(int n)
  28.      {
  29.          for (int d = n; d > 0; d--)
  30.              tower[1].push(d);
  31.          display();
  32.          move(n, 1, 2, 3);         
  33.      }
  34.      /* Recursive Function to move disks */
  35.      public static void move(int n, int a, int b, int c)
  36.      {
  37.          if (n > 0)
  38.          {
  39.              move(n-1, a, c, b);     
  40.              int d = tower[a].pop();                                             
  41.              tower[c].push(d);
  42.              display();                   
  43.              move(n-1, b, a, c);     
  44.          }         
  45.      }
  46.      /*  Function to display */
  47.      public static void display()
  48.      {
  49.          System.out.println("  A  |  B  |  C");
  50.          System.out.println("---------------");
  51.          for(int i = N - 1; i >= 0; i--)
  52.          {
  53.              String d1 = " ", d2 = " ", d3 = " ";
  54.              try
  55.              {
  56.                  d1 = String.valueOf(tower[1].get(i));
  57.              }
  58.              catch (Exception e){
  59.              }    
  60.              try
  61.              {
  62.                  d2 = String.valueOf(tower[2].get(i));
  63.              }
  64.              catch(Exception e){
  65.              }
  66.              try
  67.              {
  68.                  d3 = String.valueOf(tower[3].get(i));
  69.              }
  70.              catch (Exception e){
  71.              }
  72.              System.out.println("  "+d1+"  |  "+d2+"  |  "+d3);
  73.          }
  74.          System.out.println("\n");         
  75.      }
  76.  }

Enter number of disks
5
  A  |  B  |  C
---------------
  1  |     |
  2  |     |
  3  |     |
  4  |     |
  5  |     |
 
 
  A  |  B  |  C
---------------
     |     |
  2  |     |
  3  |     |
  4  |     |
  5  |     |  1
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
  3  |     |
  4  |     |
  5  |  2  |  1
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
  3  |     |
  4  |  1  |
  5  |  2  |
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |
  4  |  1  |
  5  |  2  |  3
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
  1  |     |
  4  |     |
  5  |  2  |  3
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
  1  |     |
  4  |     |  2
  5  |     |  3
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |  1
  4  |     |  2
  5  |     |  3
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |  1
     |     |  2
  5  |  4  |  3
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |
     |  1  |  2
  5  |  4  |  3
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |
  2  |  1  |
  5  |  4  |  3
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
  1  |     |
  2  |     |
  5  |  4  |  3
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
  1  |     |
  2  |  3  |
  5  |  4  |
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |
  2  |  3  |
  5  |  4  |  1
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |  2  |
     |  3  |
  5  |  4  |  1
 
 
  A  |  B  |  C
---------------
     |     |
     |  1  |
     |  2  |
     |  3  |
  5  |  4  |
 
 
  A  |  B  |  C
---------------
     |     |
     |  1  |
     |  2  |
     |  3  |
     |  4  |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |  2  |
     |  3  |
  1  |  4  |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |
     |  3  |  2
  1  |  4  |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |  1
     |  3  |  2
     |  4  |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |  1
     |     |  2
  3  |  4  |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |
     |  1  |  2
  3  |  4  |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |
  2  |  1  |
  3  |  4  |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
  1  |     |
  2  |     |
  3  |  4  |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
  1  |     |
  2  |     |  4
  3  |     |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |  1
  2  |     |  4
  3  |     |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |  1
     |     |  4
  3  |  2  |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |
     |  1  |  4
  3  |  2  |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |  3
     |  1  |  4
     |  2  |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |
     |     |  3
     |     |  4
  1  |  2  |  5
 
 
  A  |  B  |  C
---------------
     |     |
     |     |  2
     |     |  3
     |     |  4
  1  |     |  5
 
 
  A  |  B  |  C
---------------
     |     |  1
     |     |  2
     |     |  3
     |     |  4
     |     |  5

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.