ISC Practicals and Theory - Tower of Hanoi (Recursive Technique) (OOP)

This version of the Tower of Hanoi is written as a class: an object stores the number of disks, a parameterised constructor sets it up, and each method does one job. The solving method hanoi() calls itself, so the recursion is the core of the program. It prints every move and compares the number of moves with $2^n - 1$.

Definition

Three pegs hold disks of different sizes, largest at the bottom. All $n$ disks start on peg A and must reach peg C, using B as a spare. One disk moves at a time, only a top disk can move, and a larger disk is never put on a smaller one. The minimum number of moves is $2^n - 1$, for example $2^2 - 1 = 3$ for two disks.

The program accepts $n$ from 1 to 10. Every move is printed, so $n = 10$ prints $2^{10} - 1 = 1023$ moves; the sample runs below use small values of $n$ to keep the output short.

Algorithm

1. main reads num, creates the object t with new TowerOfHanoi(num); the constructor stores it in n and sets moves to 0.
2. isValid() returns true only when n is from 1 to 10. If it returns false, main prints an error and nothing else runs.
3. hanoi(d, from, to, via) does the recursion:
   • If d == 0 there is nothing to move, so it returns (base case).
   • Call hanoi(d - 1, from, via, to) to move the top d - 1 disks to the spare peg.
   • Add 1 to moves and print Move disk d from <from> to <to>.
   • Call hanoi(d - 1, via, to, from) to bring the d - 1 disks onto disk d.
4. formula() finds $2^n - 1$ with a loop that doubles a value n times, without Math.pow.
5. showTotal() prints moves and formula(); they must be equal.

Program

The constructor stores the number of disks, isValid() checks the range, hanoi() is the recursive method, formula() computes $2^n - 1$ and showTotal() prints both totals.

import java.util.Scanner;

/**
 * Class TowerOfHanoi: an object holds a puzzle with n disks and solves it recursively.
 */
public class TowerOfHanoi
{
    int n;      // number of disks in the puzzle
    int moves;  // number of moves made so far

    /**
     * Parameterised constructor.
     * @param nn number of disks to store in n
     */
    TowerOfHanoi(int nn)
    {
        n = nn;
        moves = 0;   // no move made yet
    }

    /**
     * Checks whether the number of disks is in the allowed range 1 to 10.
     * @return true if 1 <= n <= 10, otherwise false
     */
    boolean isValid()
    {
        return n >= 1 && n <= 10;
    }

    /**
     * Recursive method: moves d disks from peg 'from' to peg 'to' using peg 'via',
     * printing every move.
     * @param d    number of disks to move
     * @param from the peg the disks start on
     * @param to   the peg the disks must reach
     * @param via  the spare peg used for help
     */
    void hanoi(int d, char from, char to, char via)
    {
        if (d == 0)   // base case: no disk to move, so stop
            return;
        hanoi(d - 1, from, via, to);   // d-1 disks go from 'from' to the spare peg
        moves++;                       // count the move of disk d
        System.out.println("Move disk " + d + " from " + from + " to " + to);
        hanoi(d - 1, via, to, from);   // d-1 disks go from the spare peg to 'to'
    }

    /**
     * Calculates 2^n - 1 with a loop, without Math.pow.
     * @return the minimum number of moves for n disks
     */
    int formula()
    {
        int p = 1;
        for (int i = 1; i <= n; i++)   // multiply by 2, n times
            p = p * 2;
        return p - 1;
    }

    /** Prints the moves counted by the recursion and the value of 2^n - 1. */
    void showTotal()
    {
        System.out.println("Total number of moves = " + moves);
        System.out.println("2^n - 1 = " + formula());
    }

    /**
     * main: reads n, creates the object and calls the methods.
     * @param args command line arguments (not used)
     */
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);   // Scanner for input
        System.out.print("Enter the number of disks (1 to 10): ");
        int num = sc.nextInt();                // number of disks typed by the user
        TowerOfHanoi t = new TowerOfHanoi(num); // object of the class
        if (t.isValid())
        {
            t.hanoi(num, 'A', 'C', 'B');
            t.showTotal();
        }
        else
            System.out.println("Invalid input. Number of disks must be from 1 to 10.");
    }
}

Variable description table

Sample input and output

Enter the number of disks (1 to 10): 2
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Total number of moves = 3
2^n - 1 = 3

Enter the number of disks (1 to 10): 3
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
Total number of moves = 7
2^n - 1 = 7

Enter the number of disks (1 to 10): 0
Invalid input. Number of disks must be from 1 to 10.

Dry run

Input: num = 2. main calls t.hanoi(2, 'A', 'C', 'B'). Calls are numbered in the order they start. This void method returns nothing, so what carries back up is the running value of moves.

Call 5 returns to call 1, which returns to main. showTotal() prints Total number of moves = 3, and formula() takes p through $1 \to 2 \to 4$, giving $4 - 1 = 3$. This matches the real run for input 2 above.

Variations

1. Count only "Write a program to find the number of moves needed to shift n disks in the Tower of Hanoi, without printing the moves."
2. Peg names "Accept the names of the three pegs from the user and print the moves using those names."
3. Return the count "Write a recursive method that returns the number of moves for n disks."