Computer Science 225
Advanced Programming

Spring 2017, Siena College

Home     Syllabus     Schedule     Examples

Hanoi BlueJ Project

Click here to download a BlueJ project for Hanoi.

Hanoi Source Code

The Java source code for Hanoi is below. Click on a file name to download it.

Hanoi.java

import java.util.Stack;

/**
 * Example Hanoi: a demonstration of recursion to solve the Towers of Hanoi
 * problem.
 *
 * @author Jim Teresco, Siena College, Computer Science 225, Spring 2017
 *
 */

public class Hanoi {

    /** the pins on which the discs sit */
    private Stack<Integer> pins[];
    
    /** the total number of discs */
    private int numDiscs;
    
    /**
     * Construct an instance of the pins and discs for the given size problem
     * 
     * @param numDiscs the number of discs to be moved during the game
     */
    public Hanoi(int numDiscs) {
        
        this.numDiscs = numDiscs;
        pins = new Stack[3];
        pins[0] = new Stack<Integer>();
        pins[1] = new Stack<Integer>();
        pins[2] = new Stack<Integer>();
        
        for (int discSize = numDiscs; discSize >= 1; discSize--) {
            pins[0].push(discSize);
        }
    }
    
    /**
     * Solve the problem, moving the discs from pin 1 to pin 2 using pin 3 for intermediate storage
     * 
     * @return the total number of discs moved
     */
    public int solve() {
        
        print();
        return solve(numDiscs, 0, 1, 2);
    }
    
    /**
     * Recursive method to move a given number of discs from a given pin to another,
     * using a thirds as the intermediate storage.
     * 
     * @param numToMove number of discs that need to be moved
     * @param fromPin pin that contains the discs at the start
     * @param toPin pin that the discs should occupy at the end
     * @param usingPin pin available to use for intermediate storage
     * 
     * @return the number of discs moved to accomplish the movement
     */
    protected int solve(int numToMove, int fromPin, int toPin, int usingPin) {
        
        System.out.println("solve: move " + numToMove + " discs from pin " + fromPin + " to pin " +
            toPin + " using pin " + usingPin);
        
        // our base case is the movement of a single disc
        if (numToMove == 1) {
            int discToMove = pins[fromPin].pop();
            System.out.println("Base case: move disc " + discToMove + " from pin " + fromPin + 
                " to pin " + toPin + ".");
            pins[toPin].push(discToMove);
            print();
            return 1;
        }
        
        // otherwise, we'll move all but the last off of fromPin to usingPin, then the one disc
        // from fromPin to toPin, then the ones we moved to usingPin onto toPin
        int moves = solve(numToMove - 1, fromPin, usingPin, toPin);
        int discToMove = pins[fromPin].pop();
        System.out.println("Recursive case: move disc " + discToMove + " from pin " + fromPin + 
                " to pin " + toPin + ".");
        pins[toPin].push(discToMove);
        print();
        moves += solve(numToMove - 1, usingPin, toPin, fromPin);
        return moves + 1;
    }
    
    /**
     * Print an ASCII graphics representation of the current disc configuration.
     */
    private void print() {
    
        for (int i = 0; i < 3; i++) {
            System.out.println("Pin " + i + ": " + pins[i]);
        }    
    }

    /**
     * main method to solve a (text-based) instance of the Towers of Hanoi problem
     * for a given number of discs
     * 
     * @param args the number of discs should be given in args[0]
     */
    public static void main(String[] args) {
        
        int numDiscs = 0;
        // check for a parameter and that it's a number
        if (args.length != 1) {
            System.err.println("Usage: java Hanoi numDiscs");
            System.exit(1);
        }
        
        try {
            numDiscs = Integer.parseInt(args[0]);
        }
        catch (NumberFormatException e) {
            System.err.println(args[0] + " could not be converted to an integer value.");
            System.exit(1);
        }
        
        Hanoi h = new Hanoi(numDiscs);
        int totalMoves = h.solve();
        System.out.println("Done.  Moved a total of " + totalMoves + " discs.");
    
    }
}