Hi Readers,

In this blog i will provide you the Java solution for the famous Tower of Hanoi problem using Stack.

Problem definition

Tower of Hanoi is a mathematical puzzle. It is also known as Tower of Brahma or Locus' Tower. This puzzle consist of three rods in which disks can slide. There are some number of disks are placed on a rod in increasing order of their disk size form top to bottom. Now we have to transfer all the disk to another rod. Keeping in mind that.

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.

Now we have to find the of moves of disks to solve this problem. 

Java Implementation for the above problem

import java.util.Scanner;
import java.util.Stack;

public class TowerOfHanoi {
	public static int N;
	/* Creating Stack array */
	public static Stack<Integer>[] tower = new Stack[4];

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		tower[1] = new Stack<Integer>();
		tower[2] = new Stack<Integer>();
		tower[3] = new Stack<Integer>();
		/* Accepting number of disks */
		System.out.println("Enter number of disks");
		int num = scan.nextInt();
		scan.close();
		N = num;
		toh(num);
	}

	/* Function to push disks into stack */
	public static void toh(int n) {
		for (int d = n; d > 0; d--)
			tower[1].push(d);
		display();
		move(n, 1, 2, 3);
	}

	/* Recursive Function to move disks */
	public static void move(int n, int a, int b, int c) {
		if (n > 0) {
			move(n - 1, a, c, b);
			int d = tower[a].pop();
			tower[c].push(d);
			display();
			move(n - 1, b, a, c);
		}
	}

	/* Function to display */
	public static void display() {
		System.out.println("  A  |  B  |  C");
		System.out.println("---------------");
		for (int i = N - 1; i >= 0; i--) {
			String d1 = " ", d2 = " ", d3 = " ";
			try {
				d1 = String.valueOf(tower[1].get(i));
			} catch (Exception e) {
			}
			try {
				d2 = String.valueOf(tower[2].get(i));
			} catch (Exception e) {
			}
			try {
				d3 = String.valueOf(tower[3].get(i));
			} catch (Exception e) {
			}
			System.out.println("  " + d1 + "  |  " + d2 + "  |  " + d3);
		}
		System.out.println("\n");
	}

}

Output of the above program

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

Finally we have the Java solution for Tower of Hanoi puzzle. :)