Towers of Hanoi is a well known mathematical game/puzzle involving three pegs and a number of discs. The size of the discs are different and they are kept on the source peg with the smallest on the top and the biggest one on the bottom. The aim of the game is to move all the discs to a target peg with the same order using just a spare peg. The rules are,

• Only one disc can be moved at a time
• Each move consists of taking one disc from a peg and putting on top of another peg
• A disc cannot be placed over a smaller disc

History of Towers of Hanoi

French mathematician Edouard Lucas invented towers of Hanoi in 1883. One popular myth about towers of Hanoi suggests that there was a temple in India where priests worked on solving a 64 disc towers of Hanoi puzzle (known as tower of Brahma). Priests believed that when the last move of the puzzle is completed, world will end. Interestingly if the moves are made at the rate of one move per second, it will take more than 500 billion years to solve the puzzle!

Solving Towers of Hanoi Using Recursion

The number of steps required to move n discs from source page to target peg is (2 raised to n - 1). For example, it would take 7(2 raised to 3 - 1) steps to move 3 discs from source peg to target peg.

This puzzle can be concisely solved using recursion. Let us look at the strategy of solving towers of Hanoi with just 2 discs.

• Move disc 1 from source peg to spare peg
• Move disc 2 from source peg to target peg
• Move disc 1 from spare peg to target peg

For n number of discs we can generalize the above strategy as follows,

• Move n-1 discs from source peg to spare peg
• Move last disc from source peg to target peg
• Move n-1 discs from spare peg to target peg

The first step of moving n-1 discs from source to spare peg is identical to our original problem, only difference being that the roles of the pegs change (spare peg becomes target and target peg becomes the spare peg)! This shows that we can recursively solve Towers of Hanoi. The termination condition for recursion will be n=1.

The following Java program uses the above recursive strategy to solve Towers of Hanoi puzzle. The program will print the moves of the towers of Hanoi solution in the console.

import java.util.Scanner;

// Towers of Hanoi solution source code in Java
// Uses recursion
public class TowersofHanoi {
    public static final String SOURCE_PEG = "Source";
    public static final String TARGET_PEG = "Target";
    public static final String SPARE_PEG = "Spare";

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Please enter number of discs:");
        int numberOfDiscs = scanner.nextInt();
        solveTowersOfHanoi(numberOfDiscs, SOURCE_PEG, TARGET_PEG, SPARE_PEG);
        scanner.close();
    }

    // Solve towers of hanoi puzzle using recursion
    // Note the change roles of pegs internally
    private static void solveTowersOfHanoi(int numberOfDiscs, String sourcePeg, String targetPeg, String sparePeg) {
        if (numberOfDiscs == 1) {
            System.out.println(sourcePeg + " => " + targetPeg);
        } else {
            solveTowersOfHanoi(numberOfDiscs - 1, sourcePeg, sparePeg, targetPeg);
            System.out.println(sourcePeg + " => " + targetPeg);
            solveTowersOfHanoi(numberOfDiscs - 1, sparePeg, targetPeg, sourcePeg);
        }

    }
}

The heart of the program is the function solveTowersOfHanoi. It takes 4 parameters - number of discs to solve, source peg name, target peg name and spare peg name. It then immediately solves the problem if there is only 1 disc.

If there is more than 1 disc, the function tries to move n - 1 discs from source peg to spare peg (note that the original peg in this case becomes the spare peg!). This is recursive and hence all discs except the last one will be moved from source peg to spare peg. Then the final disc is moved from source peg to target peg. Finally n - 1 discs will be moved from spare peg to target peg in recursive mode. This completes the towers of Hanoi puzzle.