Tutorial

Tower of Hanoi - Algorithm and Implementation in Java

Published on August 3, 2022
author

Jayant Verma

Tower of Hanoi - Algorithm and Implementation in Java

The Tower of Hanoi is a classic problem in the world of programming. The problem setup consists of three rods/pegs and n disks.

The disks can be moved from one peg to another. The n disks are of different sizes.

Initially all the disks are stacked on the first tower. The disks are stacked in such a way that a disk is always over a disk bigger than itself.

Tower of Hanoi Default Setup

Tower of Hanoi setup

Fun fact : This game was invented by a French mathematician Édouard Lucas in the 19th century. It is associated with a legend of a Hindu temple where the puzzle was supposedly used to increase the mental discipline of young priests.

Problem Statement

Move all the disks stacked on the first tower over to the last tower using a helper tower in the middle. While moving the disks, certain rules must be followed. These are : 

1. Only one disk can be moved.

2. A larger disk can not be placed on a smaller disk.

So you need to move all the disks from the first tower over to the last. You can only move one disk at a time and never place a smaller disk over a larger disk.

To do this you have an extra tower, it is known as helper/auxiliary tower.

Since you can only move one disk at a time, the disk you move will have to be at the top of its tower.

Theoretical Solution to the Tower of Hanoi Problem

Let’s name the towers as A,B,C and the disks as 1,2,3.

Tower of Hanoi

We solve this question using simple recursion. To get the three disks over to the final tower you need to :

  1. Take the disk number 1 and 2 to tower B.
  2. Move disk number 3 to tower C.
  3. Take disk number 1 and 2 from B to C.

Of course, you can’t do it like this because of the constraints. However, we can use this to create a function that does it recursively.

TOH 1
Starting state

In the function we write, we will print the movement of the disks.

Implementing the Solution to Tower of Hanoi in Java

Let’s begin with understanding the two main parts of the code to solve the Tower of Hanoi problem.

1. Base case

The base case in our code is when we only have one disk. That is n=1.

 if (n == 1)
        {
            System.out.println("Take disk 1 from rod " +  from_rod + " to rod " + to_rod);
            return;
        }

2. Recursive calls

The recursive calls to solve tower of Hanoi are as follows:

 towerOfHanoi(n-1, from_rod, helper_rod, to_rod);
        System.out.println("Take disk " + n + " from rod " +  from_rod + " to rod " + to_rod);
        towerOfHanoi(n-1, helper_rod, to_rod, from_rod);
    }

These are equivalent to:

  1. Move the top n-1 disks to the auxiliary tower.
  2. Move 1 disk from source rod to destination rod.
  3. Take the n-1 disks from auxiliary disk to the destination rod.

Complete Java Implementation of Tower of Hanoi

package com.JournalDev;
public class Main {
    static void towerOfHanoi(int n, char from_rod, char to_rod, char helper_rod)
    {
        if (n == 1)
        {
            System.out.println("Take disk 1 from rod " +  from_rod + " to rod " + to_rod);
            return;
        }
        towerOfHanoi(n-1, from_rod, helper_rod, to_rod);
        System.out.println("Take disk " + n + " from rod " +  from_rod + " to rod " + to_rod);
        towerOfHanoi(n-1, helper_rod, to_rod, from_rod);
    }

    public static void main(String args[])
    {
        int n = 5;
        towerOfHanoi(n,'A','C', 'B');
    }

} 

The output for the code is:

Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 3 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C

Tower of Hanoi Output

We can understand the process using the following illustration. You can run the code for any number of disks.

The output for n=5 is :

Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 3 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C
Take disk 4 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 2 from rod C to rod A
Take disk 1 from rod B to rod A
Take disk 3 from rod C to rod B
Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 5 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C
Take disk 3 from rod B to rod A
Take disk 1 from rod C to rod B
Take disk 2 from rod C to rod A
Take disk 1 from rod B to rod A
Take disk 4 from rod B to rod C
Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 3 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C
TOH for n=5
n=5

The formula to calculate the number of steps for n disks is :

(2^n)-1

Conclusion

This is how you solve the Tower of Hanoi using recursion. Hope you had fun learning with us!

Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.

Learn more about our products

About the authors
Default avatar
Jayant Verma

author

While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.

Still looking for an answer?

Ask a questionSearch for more help

Was this helpful?
 
JournalDev
DigitalOcean Employee
DigitalOcean Employee badge
December 6, 2020

How can this be extended for t number of towers, everyone i have seen targets three towers, what about 4, 5, 6, 7… towers?

- Oluwatosin

    Try DigitalOcean for free

    Click below to sign up and get $200 of credit to try our products over 60 days!

    Sign up

    Join the Tech Talk
    Success! Thank you! Please check your email for further details.

    Please complete your information!

    Featured on Community

    Get our biweekly newsletter

    Sign up for Infrastructure as a Newsletter.

    Hollie's Hub for Good

    Working on improving health and education, reducing inequality, and spurring economic growth? We'd like to help.

    Become a contributor

    Get paid to write technical tutorials and select a tech-focused charity to receive a matching donation.

    Welcome to the developer cloud

    DigitalOcean makes it simple to launch in the cloud and scale up as you grow — whether you're running one virtual machine or ten thousand.

    Learn more