Bringing Down Towers of Hanoi - part10

So we have come to the final part of this series! As promised, we will be ending the series with the source code which solves 4 tower case (can be generalized to more towers)


For those who are new and like to give it a try before looking at the solutions, part4 is probably a good place to start, unless you are really new to Towers of Hanoi, in which case it should be part1.

I haven't yet seen a java code to solve the general case for towers of hanoi for 4 towers. If you see a code let me know. I will try to format this nicely and add some comments too later. Since earlier posts contained all explanations needed, I hope you will be able to figure out the algorithm easily. Enjoy!

package com.araaya.hanoitowers;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.StringTokenizer;

/**
 *@author Ashoka Ekanayaka
 * www.it-front.net,   www.araaya.com
 */
public class HanoiTowers4 {
    //ArrayList<Integer> source1, target1, middle1, middle2;
    //int steps = -1;
    static Hashtable<Integer, HeightInfo> table = new Hashtable<Integer, HeightInfo>();
    static {
        table.put(1, new HeightInfo(1,0,1));
    }

    public static void main(String[] args) {
        int height = Integer.parseInt(args[0]);
        ArrayList<String> towers = new ArrayList<String>(4);
        String s = "";
        for (int i=height; i>0; i--) {
            s = s + i;
            if (i != 1) {
                s= s + ",";
            }
        }
        towers.add(s);
        towers.add("");

        //s = "";
        //for (int i=2; i>0; i--) {
        //    s = s + i;
        //    if (i != 1) {
        //        s= s + ",";
        //    }
        //}
        towers.add("");

        towers.add("");
        String moveList = HanoiTowers4.getSolution(height, 4, towers);
        String[] moves = moveList.split(",");
        System.out.println(moves.length + " Moves");
        System.out.println(moveList);
    }

    public static String getSolution(int diskCount, int towerCount, ArrayList<String> towerContents) {
        ArrayList<ArrayList<Integer>> towers = new ArrayList<ArrayList<Integer>>(towerCount);
        for (int i=0; i<towerCount; i++) {
            String s = towerContents.get(i);
            ArrayList<Integer> tower = new ArrayList<Integer>(diskCount);

            if (!s.equals("")) {
                String[] disks = s.split(",");
                for (int j=0; j<disks.length; j++) {
                    tower.add(Integer.parseInt(disks[j]));
                }
            }
            towers.add(tower);
        }

        StringBuilder moveList = new StringBuilder();
        if (towerCount == 3) {
            return buildTower3(diskCount, 0, 0, 2, 1, towers, moveList).toString();
        } else if (towerCount == 4) {
            return buildTower4(diskCount, 0, 3, 1, 2, towers, moveList).toString();
        } else {
            return null;
        }
    }

    public static StringBuilder buildTower4(int height, int source, int target, int middle1, int middle2, ArrayList<ArrayList<Integer>> towers, StringBuilder moveList) {
        if (height == 0) {
            return moveList;
        }

        ArrayList<Integer> targetTower = towers.get(target);
        if (targetTower.contains(Integer.valueOf(height))) {
            buildTower4(height-1, source, target, middle1, middle2, towers, moveList);
        } else {
            ArrayList<Integer> middle1Tower = towers.get(middle1);
            ArrayList<Integer> middle2Tower = towers.get(middle2);
            if (middle1Tower.contains(Integer.valueOf(height))) {
                int temp = middle1;
                middle1 = source;
                source = temp;
            }
            if (middle2Tower.contains(Integer.valueOf(height))) {
                int temp = middle2;
                middle2 = source;
                source = temp;
            }

            int newHeight = getSteps(height).t4Height;

            buildTower4(newHeight, source, middle1, middle2, target, towers, moveList);
            if (height > 2) {
                buildTower3(height-1, newHeight, source, middle2, target, towers, moveList);
            }
            move(source, target, towers, moveList);
            print(towers);
            if (height > 2) {
                buildTower3(height-1, newHeight, middle2, target, source, towers, moveList);
            }
            buildTower4(newHeight, middle1, target, middle2, source, towers, moveList);
        }

        return moveList;
    }

    public static StringBuilder buildTower3(int height, int ceiling, int source, int target, int middle, ArrayList<ArrayList<Integer>> towers, StringBuilder moveList) {
        if (height == ceiling) {
            return moveList;
        }

        ArrayList<Integer> targetTower = towers.get(target);
        if (targetTower.contains(Integer.valueOf(height))) {
            buildTower3(height-1, ceiling, source, target, middle, towers, moveList);
        } else {
            ArrayList<Integer> middleTower = towers.get(middle);
            if (middleTower.contains(Integer.valueOf(height))) {
                int temp = middle;
                middle = source;
                source = temp;
            }
            buildTower3(height-1, ceiling, source, middle, target, towers, moveList);
            move(source, target, towers, moveList);
            print(towers);
            buildTower3(height-1, ceiling, middle, target, source, towers, moveList);
        }

        return moveList;
    }

    public static HeightInfo getSteps(int height) {
        if (table.containsKey(height)) {
            return table.get(height);
        }

        boolean optimalFound = false;
        int optimalSteps = Integer.MAX_VALUE;

        int t4 = 0;
        int steps = 0;
        for (int t4Height = height-1; !optimalFound && t4Height>0; t4Height--) {
            int t3Height = (height - 1) - t4Height;
            steps = 1 + 2*(getSteps(t4Height).steps) + 2*((1 << t3Height) - 1);
            if (steps < optimalSteps) {
                optimalSteps = steps;
                t4 = t4Height;
                System.out.println("current minimum steps for height " + height + " is : " + steps + " with " + t4Height + "-" + t3Height);
            } else {
                optimalFound = true; // no point searching beyond this. current steps are the optimal
            }
        }

        System.out.println("putting => " + height + ":" + optimalSteps + ":" + t4);
        HeightInfo info = new HeightInfo(height, t4, optimalSteps);
        table.put(height, info);

        return info;
    }

    private static void print(ArrayList<ArrayList<Integer>> towers) {
        for (ArrayList<Integer> tower : towers) {
            for (Integer i : tower) {
                System.out.print(i+",");
            }
            System.out.print(" : ");
        }
        System.out.println();
    }

    private static void move(int source, int target, ArrayList<ArrayList<Integer>> towers, StringBuilder strB) {
        ArrayList<Integer> targetTower = towers.get(target);
        ArrayList<Integer> sourceTower = towers.get(source);
        targetTower.add(sourceTower.get(sourceTower.size()-1)); // add the top most element in source to the top of target
        sourceTower.remove(sourceTower.size()-1);
        strB.append(source + 1);
        strB.append("-");
        strB.append(target + 1);
        strB.append(",");
    }
}