Bringing Down Towers of Hanoi - part 5

In the last post, I promised you to give more hints on how to solve (find the algorithm that is) general case of towers of Hanoi. Those who are new to this Hanoi business, can get up to date from earlier parts of the series.

part1
part2
part3

Let's consider the following scenario we have a tower of height 5, instead of having all stacked up neatly in the 1st tower, we have the largest ring already in tower3.






Here's what a run of my code produced.

Step 0 -> 3,2,1,0, : : 4,

Step 1 -> 3,2,1, : 0, : 4,
Step 2 -> 3,2, : 0, : 4,1,
Step 3 -> 3,2, : : 4,1,0,
Step 4 -> 3, : 2, : 4,1,0,
Step 5 -> 3,0, : 2, : 4,1,
Step 6 -> 3,0, : 2,1, : 4,
Step 7 -> 3, : 2,1,0, : 4,
Step 8 -> : 2,1,0, : 4,3,
Step 9 -> : 2,1, : 4,3,0,
Step 10 -> 1, : 2, : 4,3,0,
Step 11 -> 1,0, : 2, : 4,3,
Step 12 -> 1,0, : : 4,3,2,
Step 13 -> 1, : 0, : 4,3,2,
Step 14 -> : 0, : 4,3,2,1,
Step 15 -> : : 4,3,2,1,0,

wow! it found the biggest ring is already in where it wanted to be so finished off with the optimal solution. How do we know that was the optimal ? well, because it took exactly 15 steps, which isthe expected to solve a tower with height 4. Since 5th tile is already there for us, it is like solving a tower of height 4!

Now, then, let's make it little difficult for the computer and see. we pit the biggest ring in the MIDDLE tower at start and let's see what will happen.






Step 0 -> 3,2,1,0, : 4, :

Step 1 -> 3,2,1,0, : : 4,
Step 2 -> 3,2,1, : 0, : 4,
Step 3 -> 3,2, : 0, : 4,1,
Step 4 -> 3,2, : : 4,1,0,
Step 5 -> 3, : 2, : 4,1,0,
Step 6 -> 3,0, : 2, : 4,1,
Step 7 -> 3,0, : 2,1, : 4,
Step 8 -> 3, : 2,1,0, : 4,
Step 9 -> : 2,1,0, : 4,3,
Step 10 -> : 2,1, : 4,3,0,
Step 11 -> 1, : 2, : 4,3,0,
Step 12 -> 1,0, : 2, : 4,3,
Step 13 -> 1,0, : : 4,3,2,
Step 14 -> 1, : 0, : 4,3,2,
Step 15 -> : 0, : 4,3,2,1,
Step 16 -> : : 4,3,2,1,0,

aha! not so difficult again. Code was smart enough to know it should just move the biggest ring to the 3rd tower and it was exactly as the earlier problem.

What if we make things seriously wrong and ask it to solve ? In the normal solution path, after first 3 moves, we should be having the two smallest rings stacked in the middle tower. Let's put them on tower 3 and see.






Step 0 -> 4,3,2, : : 1,0,

Step 1 -> 4,3,2,0, : : 1,
Step 2 -> 4,3,2,0, : 1, :
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,

great! it didn't exceed 31 steps.

Now, can you come up with the code to produce this ? give it a try.... I have a one last hint. Solving is not so difficult. it will only add just few extra lines to the earlier code we have discussed.

Meanwhile, for those who have already come up with the code (but shy to post it to us on comments), we have the next stage of the challenge!

What about 4 Towers ? Solving this is easy when we do it manually and takes lesser number of steps. How about coming up with an algorithm to do that ?

This is a very interesting challenge to contemplate on......

Bringing Down Towers of Hanoi - part4

In last post, we wondered what on earth the number 2^n-1 doing (regardless of how many N rings we used!) in our little towers problem, for all the values of N.

We need to look at the recursion little deep to answer that question. As discussed earlier, solving N rings is exactly equal to do the following :

1) make a tower N-1 on the transit tower
2) move ring N from source to the final destination
3) make a tower N-1 on final destination

That involved 2 towers with height N-1 and moving of one ring. Similarly making a tower of N-1 will be equal to making 2 towers of N-2 and moving a ring. if we expand this for 3 ring case:

tower of 3 = 2 * (tower of 2) + 1 = 2 * (2*(tower of 1) +1) + 1 = 2 * (2*(1) +1) + 1 = 7 = 2³ - 1
(since making a tower of 1 always takes one move)

so, making a tower of 3 involved making 2 towers of 2 and 1 move.
that is, 4 towers of 1 and 2 + 1 moves.
that is, 2^(3-1) towers of 1 and 2¹ + 2⁰ moves. (making a tower of 1 takes just 1 move)
that is, 2^n-1 + (2^{n-2 +} 2^n-3 + 2^n-4 + ... + 2⁰⁾

Total Steps = 2^n-1 + (2^{n-2 +} 2^n-3 + 2^n-4 + ... + 1)

but the sum of sequence (2^{n-2 +} 2^n-3 + 2^n-4 + ... + 1) = 2^n-1 - 1

Hence total steps = 2^n-1 + 2^n-1 - 1 = 2 * (2^n-1 ) - 1 = 2ⁿ-1 !!

Wow, now we know why it has to be 2ⁿ-1 always !!

Our series is only just starting to get interesting! Now to the today's challenge :

We can now write a nice recursive function to solve the puzzle. However, what we are solving is actually a subset of the problem. We have so far considered cases where all the rings are in tower 1. How about we removing that restriction, how about letting the rings to be anywhere on 3 towers (as long as a bigger ring is not upon a smaller). Can we come up with the code to resolve that ?

In fact, this can be considered as the general case in Towers of Hanoi. What we have discussed in earlier posts was just a specific subset of it. In the next post, we will come with few more hits on how to approach that.

Meanwhile, try it out yoursef!

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

}

}

Bringing Down Towers of Hanoi - part1

Hope this post will not bring as much destruction as it's title suggests. In fact, we are not interested in bringing down any single tower in Hanoi, not even in any where else for that matter. What we would be doing is to brining down the problem of Towers of Hanoi into the levels we can understand it. Of course, if that was the title, we wouldn't probably be in here reading this right now would we ?

Towers of Hanoi is a popular puzzle, first introduced by the French mathematician Édouard Lucas in 1883. (However, some do maintain that the puzzle is much older than that) Those who are not familiar with the puzzle can learn all about it from here. There is a particular interest on this puzzle by the hacker (programmer, developer, coder) community mainly due to the fact that it has been taught in many 1st year CS courses throughout the world. The puzzle is a great example to demonstrate the power of recursion.

However, Towers of Hanoi is a deep enough problem that one can do it for a PhD. It could go many levels in depth and complexity. The most simplest version, I guess most of our readers have already studied in first year. Let's approach the problem step by step. If you are not a programmer and/or haven't done this problem before consider yourself lucky! you got an opportunity to have a fresh look at a very interesting problem and reap all the satisfaction of finding the solution on your own! Oh boy, this series gonna be a bit longer one....

Ready to jump in ? Ok, let's bring them down then!



Problem is to move all the rings from first tower into the third tower, one buy one. Here's the catch : you can not ever put a bigger ring on top of a smaller ring. That's why you have been provided with a middle tower, to transit.

Can you solve this your self ? of course you can. (animation at top of the page) All it need is some patience...

Now can we design a computer program to solve this. let's give it a try ....

Hint :
1) Solve it by hand for fewer number of rings and think recursively.
2) Consider three towers as three arrays. One has digits 0 to 9 in that order at start. At the end of the program execution, we need to have all digits in the 3rd array in the proper order.

We will see the answer to this basic version of the problem in the next article by the form of a peace of small, executable code. Remember, we would be upping the ante a bit in the next article and things would get more and more challenging and fun as we go on.....

So, do try it! give it a shot if you haven't already wrote a program to solve this by your self!

Welcome !!

Welcome to our blog!

Here we will discuss and analyze the use of artificial intelligence in gaming, Game Theory, IQ enhancing games and puzzles, AI algorithms used in them etc...

Creating games for PC and smart phones (iphone, android, windows mobile) is our hobby. We intend to share our experience and passion with our readers.

Stay tuned for up coming articles on :

Planet Wars (ai contest from Google) and our experience.

Towers of Hanoi : this is covered in many 1st year CS courses on AI. Here we intend to go little deeper, one step at a time ..

MasterMind : The classic board game.

Dual : An addictive yet simple board and puzzle game developed as a new and own concept.

15 Puzzle : you know it! most simplest of board games out there. or is it ?

and many more.....

If you have interesting thoughts, ideas games and algorithms to share, you are welcome to comment in here.