Question

Program a solver for the Towers of Hanoi problem presented below. Submit the
following to canvas: Hanoi.java, Driver.java (contains your main method). This is an
individual project. Students may discuss solutions to the problem but may not share code
with one another. I will discuss this project during our next lecture.
Rules:
a) There are three Pillars (Pillar1, Pillar2, Pillar3).
b) There are N number of disks of increasing size (disk size is indicated by an integer).
c) At the start, all disks are stacked on one of the pillars.
d) At no point can a disk of larger size be placed above a disk of smaller size (including
the start state).
e) You have to move all disks from the start pillar to a target pillar.
f) Only one disk can be moved at a time.

Sample Run:
Hanoi mySolver = new Hanoi(3,1,3);
//the first parameter is the number of disks
//the second parameter is the start pillar
//the third parameter is the target

The output should be:
My Solution is:
t0 Pillar1: 3 2 1
t0 Pillar2:
t0 Pillar3:
t1 Pillar1: 3 2
t1 Pillar2:
t1 Pillar3: 1
t2 Pillar1: 3
t2 Pillar2: 2
t2 Pillar3: 1
t3 Pillar1: 3
t3 Pillar2: 2 1
t3 Pillar3:
t4 Pillar1:
t4 Pillar2: 2 1
t4 Pillar3: 3
t5 Pillar1: 1
t5 Pillar2: 2
t5 Pillar3: 3
t6 Pillar1: 1
t6 Pillar2:
t6 Pillar3: 3 2
t7 Pillar1:
t7 Pillar2:
t7 Pillar3: 3 2 1

Answer 1

Tower of hanoi problem is quite simple if you understand the pattern.

Let us name three pillars as startPillar, endPillar, tempPillar where startPillar is the pillar from where we need to shift the disk, endPillar is pillar to which we have to shift all the pillars, and tempPillar is a pillar used as an intermediate pillar to store the disks. When you do an exercise of transferring 3 disks from pillar1 to pillar3 using pillar2, you will notice that there is a pattern,

• first we shift 2 disc from pillar1 to pillar2 (another tower of hanoi problem, but endPillar exchanges its place with tempPillar)
• then we shift last disc from pillar1 to pillar3
• then we need to shift 2disc from pillar2 to pillar3 (another tower of hanoi problem, but startPillar exchanges its place with tempPillar)

In general, we can conclude the algorithm that,

• shift (n-1) disc from pillar1 to pillar2 using pillar3
• shift 1 disc from pillar1 to pillar3
• shift (n-1) disc from pillar2 to pillar3 using pillar1

This can be achieved using recursion. we need to call the same problem, but with different pillar positions.

I have given an example of such a recursive function solution below with appropriate comments that will help with your understanding.

To store the discs at any point, I have used stack data structure, as adding and removing of disc from a pillar is in a form of stack, LIFO.

Driver.java

public class Driver {
    public static void main(String[] args) {
        Hanoi h = new Hanoi(3, 1, 3);
    }
}

Hanoi.java

import java.util.Stack;

public class Hanoi {
    // array of stacks to store the disc contents for all the pillars
    public static Stack<Integer>[] pillar = new Stack[4];

    // stepcount to measure the number of steps
    public int stepCount = 0;

    Hanoi(int numOfDisc, int startPillar, int endPillar) {

        pillar[1] = new Stack<Integer>();
        pillar[2] = new Stack<Integer>();
        pillar[3] = new Stack<Integer>();

        // initially push everything in pillar1
        for (int disc = numOfDisc; disc > 0; disc--)
            pillar[startPillar].push(disc);

        int tempPillar = 0;
        // set the position of tempPillar
        if (startPillar == 1 && endPillar == 2)
            tempPillar = 3;
        if (startPillar == 2 && endPillar == 3)
            tempPillar = 1;
        if (startPillar == 1 && endPillar == 3)
            tempPillar = 2;

        // print initial state
        print();
        solveHanoi(numOfDisc, startPillar, endPillar, tempPillar);
    };

    // hanoi solver using the algorithm mentioned above
    void solveHanoi(int numOfDisc, int startPillar, int endPillar, int tempPillar) {
        if (numOfDisc > 0) {
            // shift (n-1) disc from pillar1 to pillar2 using pillar3
            solveHanoi(numOfDisc - 1, startPillar, tempPillar, endPillar);

            // shift 1 disc from pillar1 to pillar3
            int disc = pillar[startPillar].pop();
            pillar[endPillar].push(disc);

            // print the change in position of discs
            print();

            // shift (n-1) disc from pillar2 to pillar3 using pillar1
            solveHanoi(numOfDisc - 1, tempPillar, endPillar, startPillar);
        }
    }

    // print pillar1, pillar2, pillar3 respectively
    void print() {
        System.out.println("t" + stepCount + " Pillar1 " + pillar[1].toString());
        System.out.println("t" + stepCount + " Pillar2 " + pillar[2].toString());
        System.out.println("t" + stepCount + " Pillar3 " + pillar[3].toString());
        System.out.println();
        // increment the number of steps
        stepCount++;
    }
}