Java Program to Solve Tower of Hanoi Problem 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.

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

If you liked this Java Program, kindly share, recommend or like below!

Subscribe Newsletter & Posts
About

Manish Bhojasia, a technology veteran with 17+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer and SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage & Cluster Administration, Advanced C Programming, SAN Storage Technologies, SCSI Internals and Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him below.


Sanfoundry Training Center of Excellence (CoE)

Manish Bhojasia, a technology veteran with 17+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer and SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage & Cluster Administration, Advanced C Programming, SAN Storage Technologies, SCSI Internals and Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him below.


Follow Manish & Sanfoundry