Program to solve "Tower of Hanoi" problem

Posted by N.K. Chauhan on Mar 31, 2024

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

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

Example 1: Moves to solve tower of hanoi with 3 disks.

Input: n=3, towers: A,B,C
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.

Example 2: Moves to solve tower of hanoi with 4 disks.

Input: n=4, towers: A,B,C
Output:

Move disk: 1 from: A to: B.
Move disk: 2 from: A to: C.
Move disk: 1 from: B to: C.
Move disk: 3 from: A to: B.
Move disk: 1 from: C to: A.
Move disk: 2 from: C to: B.
Move disk: 1 from: A to: B.
Move disk: 4 from: A to: C.
Move disk: 1 from: B to: C.
Move disk: 2 from: B to: A.
Move disk: 1 from: C to: A.
Move disk: 3 from: B to: C.
Move disk: 1 from: A to: B.
Move disk: 2 from: A to: C.
Move disk: 1 from: B to: C.


Solutions

Method 1: Recursion

Lets assume we have three towers: A (Source Tower), B (Auxiliary Tower), C (Destination Tower).

If there was only one disk we would have move that from A to C and thats it, this will make the base condition.

Now if there are more than 1 disk, we should remove all but 1 from A to B recursively; so that we can move remaining one biggest disk from A to C.

Now all we have to do is to move all disks (moved from A in previous step) from B to C recursively.

package com.cb.recursion;

/*
 * Assume towers:
 * A (sourceTower),
 * B (auxTower), C (desTower)
 * */
public class R14_TowerOfHanoi {

    public static void move(int noOfDisk, char sourceTower, char auxTower, char desTower) {

        // if single disk in A, move it to C
        if (noOfDisk == 1) {
            moveSingleDisk(1, sourceTower, desTower);
            return;
        }

        // Move n-1 disks from A to B, so that the remaining last disk in A can be moved to C
        move(noOfDisk - 1, sourceTower, desTower, auxTower);

        // Move remaining disk in A to C
        moveSingleDisk(noOfDisk, sourceTower, desTower);

        // Move n-1 disks (came from A in first step) from B to C
        move(noOfDisk - 1, auxTower, sourceTower, desTower);
    }

    // just printing
    private static void moveSingleDisk(int diskNumber, char source, char dest) {
        System.out.println("Move disk: " + diskNumber + " from: " + source + " to: " + dest + ".");
    }

    public static void main(String[] args) {
        move(3, 'A', 'B', 'C');
    }
}

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.

Complexity

For every disk two recursive case originates, so Time Complexity is O(2^n) and the Space Complexity is O(1).

Related


Check if an integer array is sorted or not

Calculate the Power of a Number (n^p)

Print numbers from a given number to 0

Sum of the digits of a given number

Print spelling for a given number

Count ways to reach the nth stair

Write a program to reverse a string

Calculate factorial of a given number

Print numbers from 0 to a given number

Program for printing nth Fibonacci Number