Tuesday, May 24, 2011

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(",");
    }
}

7 comments:

  1. Hi, I'm a Computer Scientist and since my AI class I've been playing with optimizations for Hanoi Tower and multi-pegs tower...

    I've trying to create a general formula to find the optimal number of steps as a function of number of towers and number of rings. I got to this: http://en.wikipedia.org/wiki/Talk:Tower_of_Hanoi#Mnimal_number_of_moves_for_any_number_of_pegs_and_discs

    I didn't got time to test it very well or to explain how I got to it, but I'd like to share that and see if you are interested in testing it validity.

    ReplyDelete
  2. #sublinhado, Thanks for visiting and the comment!

    Your research seems very interesting and I wish you all the best.

    If your formula and the proof is indeed correct, that would be of some achievement! AFAIK a mathematical formula for the general case of n towers and m disks is still not available. (unless you cracked it)

    What they have at the moment is a conjecture. They have a set of numbers for the steps needed for each m and n and those seems to be the optimal values as well. I tested those numbers with my algorithm and i'm getting the same results too. However, no one has so far proved that those are indeed the best case numbers and there is no better answers....

    you can run the program for the 4 tower case and see the results.

    I will have a detailed look at your studies and give you inputs if I have any, however my main interest in programming and AI but I'm not too much into mathematics. (I was, at one time but no longer have the time)

    Once again, thanks and all the best!

    ReplyDelete
  3. #Ashoka, Thanks for your response.

    I'm more into programming, than mathematic either. This formula comes from more pattern analysis than anything else. I made a algorithm for it about 2 years ago, but just found how to write it in a mathematical formula recently.

    I will need some help to prove it mathematically also. What I discovered is acctualy simple.
    1 - Each disc makes a power of 2 moves;
    2 - The increase in the number of moves for each additional disc and peg is related to the Pascal's Triangle, or better, combination.
    3 - Each column of the Pascal's Triangle represents the number of pegs. The column 0 stands for 3 pegs, column 1 for 4 pegs, and so on... (col = pegs-3)
    4 - Each row represents a group of discs that have the same number of moves. The first group (group 0) makes 2^0 moves, the second group (group 1) makes 2^1 moves, and so on...
    5 - The result of the combination C(col,row) is the exact ammount of discs on that group.
    6 - The relation between the group number and the row number is (pegs-3). So, for 3 pegs, group 0 is on row 0 (3-3), for 4 pegs, group 0 is on row 1 (4-3), and so on...
    7 - The combination in factor of groups (n) and pegs (p), C(row,col) = C(n+p-3, p-3).

    After I found all this relations, I could make an algorithm and later a mathematical formula. But I still need help with the mathematical proof, or a proof that it is wrong.
    I'm looking for help, also to write the inequation to find n as a function.

    Now I'm trying to find the number of optimal solutions for a given number of pegs and discs. This is all just for fun...

    Thanks for your interest! And I'll let you know if I make any progress.

    ReplyDelete
  4. This is nice coding for the game tower of hanoi i really like to play games i am a game lover and this blog is very nice i am happy with the description thank you so much for sharing...


    Microsoft Office Promo Code

    ReplyDelete
  5. Maakali Packers & Movers is a Cargo Packers and Movers in Lucknow, providing packers movers services, professional warehousing services, goods moving services, corporate relocation services, loading unloading services.

    Mr.S S Mishra

    Maakali packers movers and transportation

    ReplyDelete
  6. This is the game of intelligence thanks for sharing this blog...

    mp3 quran

    ReplyDelete