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;
}
}
|
|