Bringing Down Towers of Hanoi - part3

Today, we will see the code to solve Towers of Hanoi. A simple recursive function which does following... (If we have 10 rings, N would be 10)

1) build a tower of height N-1 on tower2 (from tower1)
2) move the ring N from tower1 into tower3
3) build a tower of height N-1 (again) but this time on top of tower3 (from tower2)

but we have to do it recursive for N-1 (that is 9) too then also for 8 etc .. For those who are new to the series or like to give another attempt to write the code on their own, you can visit here and here for details and motivation.

The Complete Java code can be found at the end of this post. (it would be straightforward to write this in any other language) You can run it passing the number of rings as a parameter for the main method. ie : java HanoiTowers 5 and it will display the proceedings in a text base command line display.

This is the output I got for 5 rings :
Step 0 -> 4,3,2,1,0, : :
Step 1 -> 4,3,2,1, : : 0,
Step 2 -> 4,3,2, : 1, : 0,
Step 3 -> 4,3,2, : 1,0, :
Step 4 -> 4,3, : 1,0, : 2,
Step 5 -> 4,3,0, : 1, : 2,
Step 6 -> 4,3,0, : : 2,1,
Step 7 -> 4,3, : : 2,1,0,
Step 8 -> 4, : 3, : 2,1,0,
Step 9 -> 4, : 3,0, : 2,1,
Step 10 -> 4,1, : 3,0, : 2,
Step 11 -> 4,1,0, : 3, : 2,
Step 12 -> 4,1,0, : 3,2, :
Step 13 -> 4,1, : 3,2, : 0,
Step 14 -> 4, : 3,2,1, : 0,
Step 15 -> 4, : 3,2,1,0, :
Step 16 -> : 3,2,1,0, : 4,
Step 17 -> 0, : 3,2,1, : 4,
Step 18 -> 0, : 3,2, : 4,1,
Step 19 -> : 3,2, : 4,1,0,
Step 20 -> 2, : 3, : 4,1,0,
Step 21 -> 2, : 3,0, : 4,1,
Step 22 -> 2,1, : 3,0, : 4,
Step 23 -> 2,1,0, : 3, : 4,
Step 24 -> 2,1,0, : : 4,3,
Step 25 -> 2,1, : : 4,3,0,
Step 26 -> 2, : 1, : 4,3,0,
Step 27 -> 2, : 1,0, : 4,3,
Step 28 -> : 1,0, : 4,3,2,
Step 29 -> 0, : 1, : 4,3,2,
Step 30 -> 0, : : 4,3,2,1,
Step 31 -> : : 4,3,2,1,0,

Step 0 above was the starting state of 3 towers (separated by ":" s). To solve the entire problem, it took only 4 lines of code!

private void buildTower(int height, ArrayList source, ArrayList target, ArrayList middle) {
if (height < 0) return;
buildTower(height-1, source, middle, target);
move(source, target); // just moves the top ring from source into top of target
buildTower(height-1, middle, target, source);
}

That was all which took for solving the whole puzzle, Now, that's the power of recursion!

Now to the second part of the challenge : The puzzle above took exactly 31 moves. Similarly you would see puzzle with 10 will take 1023. 4 rings will take 15. N rings will take exactly 2ⁿ - 1 steps.

How did that happen ? can we explain how on earth the value 2ⁿ - 1 comes in for all values of N ? what is the significance of 2 there ? Try to figure it out, we will discuss the explanation in the next post.

Meanwhile...

Following is the complete Java code for today's post. Enjoy!

package com.araaya.hanoitowers;

import java.util.ArrayList;

/**

*@author Ashoka Ekanayaka

* www.it-front.net, www.araaya.com

*/

public class HanoiTowers {

static ArrayList source1, target1, middle1;

static int steps = -1;

public static void main(String[] args) {

int height = Integer.parseInt(args[0]);

source1 = new ArrayList(height);

target1 = new ArrayList(height);

middle1 = new ArrayList(height);

for (int i=height-1; i >= 0; i--) {

source1.add(i);

}

print();

buildTower(height-1, source1, target1, middle1);

}

private static void buildTower(int height, ArrayList source, ArrayList target,
ArrayList middle) {

if (height < 0) return;
buildTower(height-1, source, middle, target);

move(source, target);

print();

buildTower(height-1, middle, target, source);

}

private static void print() {

steps++;

System.out.print("Step " + steps + " -> ");

for (Integer i : source1) {

System.out.print(i+",");

}

System.out.print(" : ");

for (Integer i : middle1) {

System.out.print(i+",");

}

System.out.print(" : ");

for (Integer i : target1) {

System.out.print(i+",");

}

System.out.println();

}

private static void move(ArrayList source, ArrayList target) {

target.add(source.get(source.size()-1)); // move top element in source to top of target

source.remove(source.size()-1);

}

}