Home » Java Programs

Java program for Tower of Hanoi

Tower of Hanoi program in Java: Here, we are implementing a Java program to solve the Tower of Hanoi.
Submitted by Indrajeet Das, on December 13, 2018

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move all disks from source rod to destination rod using the third rod (say auxiliary). The rules are:

1. Only one disk can be moved at a time.
2. A disk can be moved only if it is on the top of a rod.
3. No disk can be placed on the top of a smaller disk.

Print the steps required to move n disks from source rod to destination rod. Source Rod is named as 'a', auxiliary rod as 'b' and destination rod as 'c'.

Input format: Integer n

Output format: Steps in different lines (in one line print source and destination rod name separated by space).

Example:

    Sample Input:
    2

    Sample Output:
    a b
    a c
    b c

Explanation:

This is one of the famous problems on recursion. To solve this, let's assume the steps taken for 2 disks. Let’s assume Rod A, B, and C and we have to shift the disks from A to B. First, we shift the smaller disk to C, then we shift the larger disk to B, and at last, put the smaller disk from C to B.

Therefore, for N disks, lets recursion shifts N-1 disks to C, and we will shift the last disk to B and again let recursion shifts rest of the disk to C. Using this, we will be able to solve the problem.

Algorithm:

Declare a recursive function towerOfHanoi with parameters (int disk, char source, char auxiliary, char destination)

• STEP 1: Base Case: If(disk == 0) return;
• STEP 2: Base Case: If(disk == 1) Print Source to Destination
• STEP 3: Recursive Case: towerOfHanoi(disk -1, source, destination, auxiliary)
• STEP 4: Print Source to Destination
• STEP 5: towerOfHanoi(disk -1, auxiliary, source,destination)

Example:

    Input : 3

    Disk 1 moved from A to C
    Disk 2 moved from A to B
    Disk 1 moved from C to B
    Disk 3 moved from A to C
    Disk 1 moved from B to A
    Disk 2 moved from B to C
    Disk 1 moved from A to C

Program:

import java.util.Scanner;

public class Main {
  //Recursive Function
  public static void towerOfHanoi(int disks, char source, char auxiliary, char destination) {
    // Write your code here
    if (disks == 0) { //Base Case 1
      return;
    }
    if (disks == 1) { //Base Case 2
      System.out.println(source + " " + destination);
      return;
    } else {
      //Shifting d-1 disk from A to C
      towerOfHanoi(disks - 1, source, destination, auxiliary);
      System.out.println(source + " " + destination);
      //Shifting d-1 disk from c to B
      towerOfHanoi(disks - 1, auxiliary, source, destination);
    }
  }

  public static void main(String[] args) {
    int disk;
    Scanner s = new Scanner(System.in);

    System.out.print("Print No of Disks: ");
    disk = s.nextInt();

    towerOfHanoi(disk, 'A', 'C', 'B');
  }
}

Output

Print No of Disks: 3
A B
A C
B C
A B
C A
C B
A B