Java‎ > ‎Recursion‎ > ‎

Towers of Hanoi

Recursive solution of Towers of Hanoi in Java *with visual aid*.

/*
 * Author: kr@compute.info
 */

package info.compute.exmaples.recursion;

import java.util.Stack;

public class TowersOfHanoi {
    Stack<Integer> fromTower = new Stack<Integer>();
    Stack<Integer> auxTower = new Stack<Integer>();
    Stack<Integer> toTower = new Stack<Integer>();
    int counter = 0;
    
    public static void main(String[] args) {
        TowersOfHanoi toh = new TowersOfHanoi();
        toh.printTowers();
        toh.solveTowersOfHanoi(4, toh.fromTower, toh.toTower, toh.auxTower);
    }
    
    public TowersOfHanoi() {
        fromTower.add(4);
        fromTower.add(3);
        fromTower.add(2);
        fromTower.add(1);
    }
    
    private void solveTowersOfHanoi(int n, Stack<Integer> fromTower, Stack<Integer> toTower, Stack<Integer> auxTower) {
        if(n < 1)
            return;
        else if(n == 1)
            moveDisc(fromTower, toTower);
        else {
            solveTowersOfHanoi(n - 1, fromTower, auxTower, toTower);
            moveDisc(fromTower, toTower);
            solveTowersOfHanoi(n - 1, auxTower, toTower, fromTower);
        }
    }
    
    private void moveDisc(Stack<Integer> fromTower, Stack<Integer>toTower) {
        toTower.add(fromTower.pop());
        printTowers();
    }
    
    private void printTowers() {
        Stack<Integer> copyFromTower = (Stack<Integer>) fromTower.clone();
        Stack<Integer> copyAuxTower = (Stack<Integer>) auxTower.clone();
        Stack<Integer> copyToTower = (Stack<Integer>) toTower.clone();
        
        System.out.println(counter++ + ".");
        System.out.println("     |          |          |     ");
        
        int z1 = 4 - copyFromTower.size();
        int z2 = 4 - copyAuxTower.size();
        int z3 = 4 - copyToTower.size();

        for(int i = 0; i < 4; i++) {
            if(z1-- > 0)
                System.out.print("     |     ");
            else
                System.out.print(getDiscVisual(copyFromTower.pop()));
            if(z2-- > 0)
                System.out.print("     |     ");
            else
                System.out.print(getDiscVisual(copyAuxTower.pop()));
            if(z3-- > 0)
                System.out.println("     |     ");
            else
                System.out.println(getDiscVisual(copyToTower.pop()));
        }
        
        System.out.println("#################################");
        try {
            Thread.sleep(500);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    
    private String getDiscVisual(Integer disc) {
        String result;
        switch(disc) {
        case 1:
            result = "    =|=    ";
            break;
        case 2:
            result = "   ==|==   ";
            break;
        case 3:
            result = "  ===|===  ";
            break;
        case 4:
            result = " ====|==== ";
            break;
        default:
            result = "     |     ";
        }
        
        return result;
    }

}
Comments