Bringing Down Towers of Hanoi - part9

As we promised in part8 of this series, In this post we are going to see few sample outputs from Tower4 program in action. Also we will discuss the algorithm behind how to determine the best breakdown of middle towers. (Remember, in four tower case, we have choices on how to distribute the disks between tower 2 and 3 when we want to move disks from tower 1 to 4)

Let's see the case of 5 disks :

6,5,4,3,2, :  : 1, : 
6,5,4,3, :  : 1, : 2,
6,5,4, : 3, : 1, : 2,
6,5,4, : 3,2, : 1, : 
6,5,4, : 3,2,1, :  : 
6,5, : 3,2,1, :  : 4,
6, : 3,2,1, : 5, : 4,
6, : 3,2,1, : 5,4, : 
 : 3,2,1, : 5,4, : 6,
4, : 3,2,1, : 5, : 6,
4, : 3,2,1, :  : 6,5,
 : 3,2,1, :  : 6,5,4,
 : 3,2, : 1, : 6,5,4,
2, : 3, : 1, : 6,5,4,
2, :  : 1, : 6,5,4,3,
 :  : 1, : 6,5,4,3,2,
 :  :  : 6,5,4,3,2,1,
17 Moves

If we look at step 8 above (in blue), we will see that the program has distributed top 5 disks as 3 : 2 in the middle 2 towers. It has then moved the 6th disk to 4th tower. It could have distributed them as 4 : 1, but has found that it will be more costly. Mini tower 3-2-1 it has created on tower2 was created using all 4 towers but the Mini tower it has created on tower3 (which has disks 4 and 5) was created using only 3 towers while keeping the already buildup content at tower 2 intact.

Once the biggest disk (disk 6) was moved to tower 4, program has created a mini tower 4-5 at top of tower4 while keeping tower 2 intact. After that step it has created a mini tower 3-2-1 on tower4 using all 4 towers.

Let's have a good look at again and make sure we understand the process! 

In general, to solve 4 tower case for n disks, we need to follow these steps :
1) find optimal numbers for x and y such that x+y=n-1

2) build a tower of hight x in tower2 using all 4 towers

3) build a tower of height y (starting from disk x+1) in tower3 while using only 3 towers (since the content we built on tower2 need to be preserved)

4) move the largest disk (which is n) from tower 1 to tower4

5) build a tower of height y on top of tower4 (starting from disk x+1) while using only 3 towers and keeping the content on tower2 intact.

6) build a tower of height x in tower4 using all 4 towers.


Above is a recursive algorithm because to build a tower of n using all 4 towers, we will have to build a tower of x using all 4 towers!

Now, only one problem remaining.
 How to decide on the best distribution between tower2 and 3 (in the example it was 3:2 and not 4:1), that is x was 3 and y was 2 how to find x and y ?

Here too we could use recursion!



Following recursive algorithm and the program is something I have come up with and haven't seen in anywhere else yet. If any of you find a similar algorithm or a better one to solve this puzzle please inform me by putting a comment here with your finding. The code for this will appear in the next post


We need some notations here to make things clearer :
Let T4(n) = 'steps to make a tower of height n using 4 towers'
Let T3(n) = 'steps to make a tower of height n using 3 towers'

Then we can express the steps needed for above 6 steps in this form :
T4(n) = 2*(T4(x)+T3(y)) +1

For instance, T4(6) = 2* (T4(3)+T3(2)) + 1 

but we know T3(m) is 2^m-1, hence T3(2) above is 2²-1 = 3
So, T4(6) = 2*T4(3)+7




To build a tower of height 1, we need just 1 step.

According to above algorithm (steps 1 to 6 given above), building a tower of 2 will need 3 steps, since n=2, x=1 and y=0 in this case. (you can work out how we arrived at number 3 as home work!)

Now that we know steps needed to build a tower of 1 and a tower of 2, can we find the steps needed to create a tower of 3 ?

We have 2 choices
n =3, x=1,y=1 and
n=3, x=2, y=0

In the first case, steps needed will be 5. (home work for readers) In the second, it will be 7! (more home work) So we go with option 1. That means T4(3) =5 !!

Now we could revisit the problem of T4(6).
Earlier we found T4(6) = 2 * T4(3) + 7
then T4(6) = 2*5 + 7 = 17  Which is exactly the number of steps our program has taken to solve!

So we could recursively find best x and y for any n

All we need now is to write the nice recursive code. We will give the readers few days to come up with that code before unraveling it in our last post of Towers Hanoi series.

After that we will move to a new game and a new problem !

Your feedback on the Hanoi Towers series so far will be greatly welcome!

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

}

}