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

The Tower of Hanoi is a puzzle with three pegs and a stack of disks of different sizes. The task is to move the whole stack from one peg to another, and recursion gives a very short solution: to move $n$ disks, first move $n-1$ disks out of the way, move the largest disk, then move the $n-1$ disks back on top of it. This program prints every move and the total number of moves.

Definition

The puzzle has three pegs, here named A (source), B (helper) and C (destination). All $n$ disks start on A, with the largest at the bottom. The rules are:

• Only one disk is moved at a time.
• Only the top disk of a peg can be moved.
• A larger disk is never placed on a smaller disk.

The minimum number of moves for $n$ disks is $2^n - 1$. For example, $n = 1$ needs $2^1 - 1 = 1$ move and $n = 3$ needs $2^3 - 1 = 7$ moves.

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.

The recursive idea for $d$ disks from peg from to peg to using peg aux:

• If $d = 1$, move that disk directly (base case).
• Otherwise move $d-1$ disks from from to aux, move disk $d$ from from to to, then move $d-1$ disks from aux to to.

Algorithm

1. In main, create the object ob of class Hanoi and call accept().
2. accept() reads n. If n is not between 1 and 10, it prints an error message and returns false, so nothing else runs.
3. Otherwise main calls move(n, 'A', 'C', 'B').
4. move(d, from, to, aux) works as follows:
   • If d == 1: add 1 to count, print Move disk 1 from <from> to <to> and return.
   • Otherwise call move(d - 1, from, aux, to).
   • Add 1 to count and print Move disk d from <from> to <to>.
   • Then call move(d - 1, aux, to, from).
5. display() prints count, and also $2^n - 1$ found by totalMoves(), which multiplies 1 by 2, n times, using a loop (no Math.pow), and subtracts 1. The two numbers must be equal.

Program

The method accept() reads and checks n, move() is the recursive method that prints the moves, totalMoves() finds $2^n - 1$ and display() prints the totals.

import java.util.Scanner;

/**
 * Class Hanoi solves the Tower of Hanoi puzzle using recursion.
 * It prints every move and the total number of moves.
 */
public class Hanoi
{
    int n;      // number of disks
    int count;  // number of moves printed so far

    /** Default constructor: sets both data members to 0. */
    Hanoi()
    {
        n = 0;
        count = 0;
    }

    /**
     * Reads the number of disks and checks that it is in the range 1 to 10.
     * @param sc the Scanner used to read input
     * @return true if n is valid, false otherwise
     */
    boolean accept(Scanner sc)
    {
        System.out.print("Enter the number of disks (1 to 10): ");
        n = sc.nextInt();
        if (n < 1 || n > 10)   // range check
        {
            System.out.println("Invalid input. Number of disks must be from 1 to 10.");
            return false;
        }
        return true;
    }

    /**
     * Recursive method: moves d disks from source peg to destination peg
     * using the third peg as the helper, printing each move.
     * @param d    number of disks to move
     * @param from the peg the disks are on
     * @param to   the peg the disks must go to
     * @param aux  the helper peg
     */
    void move(int d, char from, char to, char aux)
    {
        if (d == 1)   // base case: a single disk moves directly
        {
            count++;
            System.out.println("Move disk 1 from " + from + " to " + to);
            return;
        }
        move(d - 1, from, aux, to);   // move the top d-1 disks out of the way
        count++;
        System.out.println("Move disk " + d + " from " + from + " to " + to);
        move(d - 1, aux, to, from);   // bring the d-1 disks onto the largest disk
    }

    /**
     * Finds 2^n - 1 using a loop (no Math.pow).
     * @return the number of moves needed for n disks
     */
    int totalMoves()
    {
        int p = 1;
        for (int i = 1; i <= n; i++)   // p becomes 2^n
            p = p * 2;
        return p - 1;
    }

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

    /**
     * main: 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
        Hanoi ob = new Hanoi();                // object of the class
        if (ob.accept(sc))
        {
            ob.move(ob.n, 'A', 'C', 'B');
            ob.display();
        }
    }
}

Variable description table

Sample input and output

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): 1
Move disk 1 from A to C
Total number of moves = 1
2^n - 1 = 1

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

Dry run

Input: n = 3. main calls move(3, 'A', 'C', 'B'). The calls are numbered in the order they start. A call that has finished returns to the call that made it (the method is void, so what travels back up is the running value of count).

Call 5 then returns to call 1, which returns to main. display() prints Total number of moves = 7, and totalMoves() gives $p = 1 \to 2 \to 4 \to 8$, so $8 - 1 = 7$. This matches the real run for input 3 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."