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