Towers of Hanoi
This is a program I made for fun trying to understand the recursion of the Towers of Hanoi problem. The solution to the puzzle is very simple from a recursion point of view. Without recursion the solution seems difficult to conceptualize/develop.
It was programmed using the Processing library made for Java. It is a very simple application which is a visual representation of the solution to the problem.
There are buttons which allow you to modify the puzzle. The first two buttons decrease/increase the solution speed. The other two buttons decrease/increase the number of pegs. The more pegs, the harder the puzzle in real life, but the recursion is the same.
Your screen resolution is too small to display this program
The following is the source code for the Towers of Hanoi problem. Since it uses Processing, most of the drawing code is abstracted (so only the algorithm is truly relevant).
Your screen resolution is too small to display the program code
final int diskHeight = 10;
final int diskWidthMult = 30;
final int margin = 25;
final int pegWidth = 10;
/**
* Used as a snapshot for playing the steps of the solution
*/
class Group {
ArrayList A;
ArrayList B;
ArrayList C;
Group(ArrayList theA, ArrayList theB, ArrayList theC) {
A = cloneArrayList(theA);
B = cloneArrayList(theB);
C = cloneArrayList(theC);
}
ArrayList cloneArrayList(ArrayList theList) {
ArrayList newList = new ArrayList(theList.size());
for (int i = 0; i < theList.size(); ++i) {
Disk theDisk = (Disk) theList.get(i);
newList.add(theDisk.clone());
}
return newList;
}
}
/**
* Represents a disc displayed on the screen
*/
class Disk {
float x, y;
int wid;
color diskColour;
Disk(float theX, float theY, int theNum, color col) {
x = theX;
y = theY;
wid = theNum * diskWidthMult;
diskColour = col;
}
Disk clone() {
Disk newDisk = new Disk(x, y, 0, diskColour);
newDisk.wid = wid;
return newDisk;
}
void draw() {
fill(diskColour);
rect(x - wid / 2.0f, y, wid, diskHeight);
}
}
/**
* The puzzle itself, solves it and plays it
*/
class Game {
ArrayList PegA;
ArrayList PegB;
ArrayList PegC;
// bad: needed for drawing each step
ArrayList STATE;
int currentState;
int pegACenter;
int pegBCenter;
int pegCCenter;
int theBottom;
int theN;
boolean solved;
Game(int n) {
PegA = new ArrayList(n);
PegB = new ArrayList(n);
PegC = new ArrayList(n);
theN = n;
theBottom = 200;
STATE = new ArrayList(10);
currentState = 0;
solved = false;
// Set up PegA
pegACenter = (diskWidthMult / 2 * n) + margin;
float frequency = n / 10.0f;
for (int i = n - 1; i >= 0 ; --i) {
color col = color(sin(frequency*i + -2) * 127 + 128,
sin(frequency*i + 0) * 127 + 128,
sin(frequency*i + 2) * 127 + 128);
PegA.add(new Disk(pegACenter, theBottom + i*diskHeight, i + 1, col));
}
STATE.add(new Group(PegA, PegB, PegC));
// Set up PegB
pegBCenter = pegACenter + (diskWidthMult * n) + margin * 2;
// Set up PegC
pegCCenter = pegBCenter + (diskWidthMult * n) + margin * 2;
}
void draw() {
background(255, 255, 255);
// peg A
fill(255, 228, 181);
int pegHeight = theN * diskHeight + 25;
int pegX = pegACenter - pegWidth / 2;
rect(pegX, theBottom - 25, pegWidth, pegHeight);
Group theState = (Group)STATE.get(currentState);
for (int i = 0; i < theState.A.size(); ++i) {
Disk d = (Disk)theState.A.get(i);
d.draw();
}
// peg B
fill(255, 228, 181);
pegX = pegBCenter - pegWidth / 2;
rect(pegX, theBottom - 25, pegWidth, pegHeight);
for (int i = 0; i < theState.B.size(); ++i) {
Disk d = (Disk)theState.B.get(i);
d.draw();
}
// peg C
fill(255, 228, 181);
pegX = pegCCenter - pegWidth / 2;
rect(pegX, theBottom - 25, pegWidth, pegHeight);
for (int i = 0; i < theState.C.size(); ++i) {
Disk d = (Disk)theState.C.get(i);
d.draw();
}
}
void solveProblem() {
solve(PegA, PegC, PegB, theN);
}
void solve(ArrayList Starting, ArrayList Ending, ArrayList Extra, int numLeft) {
if (numLeft == 1) {
// If there's only one peg left move it to the end
moveDisk(Starting, Ending);
}
else {
// First move from the starting peg to the extra peg
solve(Starting, Extra, Ending, numLeft - 1);
// When that's done move the last one to the end peg
moveDisk(Starting, Ending);
// Then move all the disks on the extra peg to the end peg
solve(Extra, Ending, Starting, numLeft - 1);
}
}
void moveDisk(ArrayList Starting, ArrayList Ending) {
// Take the last element (the one on top) of starting and put it at the end of ending
Disk d = (Disk)Starting.get(Starting.size() - 1);
// Move the disk to the right x location
if (Ending == PegA) {
d.x = pegACenter;
}
else if (Ending == PegB) {
d.x = pegBCenter;
}
else if (Ending == PegC) {
d.x = pegCCenter;
}
Starting.remove(Starting.size() - 1);
Ending.add(d);
// Move the disk to the right y location
d.y = theBottom + (theN * diskHeight) - Ending.size() * diskHeight;
STATE.add(new Group(PegA, PegB, PegC));
}
}
Game g;
int initialNum = 2;
int initialSolveRate = 5;
void setup() {
size(1250, 600);
background(255, 255, 255);
g = new Game(initialNum);
frameRate(initialSolveRate);
g.solveProblem();
}
final int buttonSize = 20;
void draw() {
background(255, 255, 255);
// Draw game
g.draw();
++g.currentState;
if (g.currentState == g.STATE.size()) {
g.currentState = 0;
}
// Draw buttons //////////////
// decrease solverate
fill(123,104,238);
rect(20,20,buttonSize,buttonSize);
// increase solverate
fill(238,64,0);
rect(80,20,buttonSize,buttonSize);
line(120,10,120,30+buttonSize);
// increase number of disks
fill(123,104,238);
rect(140,20,buttonSize,buttonSize);
// decrease number of disks
fill(238,64,0);
rect(200,20, buttonSize,buttonSize);
}
void mouseClicked() {
if (mouseY >= 20 && mouseY <= 20 + buttonSize) {
boolean recreateGame = false;
// decrease solveRate
if (mouseX >= 20 && mouseX <= 20 + buttonSize) {
if (initialSolveRate != 1) {
frameRate(initialSolveRate);
}
}
// increase solveRate
else if (mouseX > 80 && mouseX <= 80 + buttonSize) {
frameRate(++initialSolveRate);
}
// decrease num disks
else if (mouseX > 140 && mouseX <= 140 + buttonSize) {
if (initialNum != 2) {
--initialNum;
recreateGame = true;
}
}
// increase num disks
else if (mouseX > 200 && mouseX <= 200 + buttonSize) {
++initialNum;
recreateGame = true;
}
if (recreateGame) {
g = new Game(initialNum);
g.solveProblem();
}
}
}