Towers of Hanoi – a Java Programming Solution

Towers of Hanoi is a game with three poles labeled A, B and C and several different-size numbered disks, each with a hole in the center. Initially, all of the disks are on pole A, with the largest disk on the bottom, then the next largest and so forth. Here is how it looks when you start the game:

towers of hanoi

The object of the game is to move all of the disks from pole A to pole B; pole C is used for temporary storage. Here are the rules of the game:

  • Only one disk may be moved at a time
  • No disk may ever be placed on top of a smaller disk
  • Other than the prohibition of rule 2 above, the top disk on any pole may be moved to either of the other two poles.

Before we write any java code to solve the towers of hanoi problem, it is important to think about it first. Imagine how you would solve it. Our example will use four disks (4-1).

Towers of Hanoi – The Brainstorming

Let us assume that our initial configuration has it such that disk 4 is in pole A and the rest of the disks are in pole C. Immediately, we are met with a dilemma: Do we move disk 1 to pole B or to pole A? Making the wrong move, we might end up with the four disks on pole C rather than pole B.

Instead of trying to figure out where disk 1 should be moved initially, we will focus our attention on disk 4, the bottom disk. We cannot move disk 4 right away obviously but eventually, disk 4 will have to be moved from pole A to B.

Does this brainstorming help us figure out how to move four disks from A to B? Well, sort of. We still need to determine how to move three disks (one at a time) from pole A to C. We can then move disk 4 from A to B. Finally, we will need to determine how to move three disks (one at a time) from C to B.

This is significant in the sense that we have moved from figuring out how to move four disks to figuring out how to move three disks. But once again, we still need to determine how to move three disks from one pole to another.

If you think about it, the above strategy can be reapplied! To move three disks from say, pole A to pole C, we first move two disks (one at a time) from A to B, then we move disk 3 from A to C, and finally, we move two disks from B to C. Continually reducing the problem, we eventually face the trivial task of moving disk 1 from one pole to another.

The number 4 is not special in Towers of Hanoi

For any positive integer n, we can easily describe how to move n disks from pole A to pole B. If n=1, we simply move disk 1 from pole A to pole B. For n > 1 however:

  • First, move n – 1 disks from pole A to pole C, using pole B as a temporary.
  • Then move disk n from pole A to pole B
  • Finally, move n – 1 from pole C to pole B, using pole A as a temporary.

This still does not solve the problem because, for example, we have not described how to move n – 1 disks from A to C. But this strategy is easily generalized by replacing the constants A, B and C with variables origin, destination, and temporary. For example, we will initially have:

  • origin = A
  • destination = B
  • temporary = C

Then the general strategy for moving n disks from origin to destination is as follows:

If n is 1, move disk 1 from origin to destination. Otherwise:

  1. Move n – 1 disks (one at a time) from origin to temporary
  2. Move disk n from origin to destination
  3. Move n – 1 disks (one at a time) from temporary to destination

The following recursive method incorporates the above strategy for moving n disks. If n = 1, the String representing the move, namely, “Move disk 1 from ” + origin + ” to ” +dest + “n” is simply returned. Otherwise, the String object returned consist of three String objects concatenated together as shown below:

[java]
/**
* Towers of Hanoi Recursive solution
*
*/
move( n – 1, origin, temp, dest)
“Move disk ” + n + ” from ” + origin + ” to ” + dest + “\n”
move( n – 1, temp, dest, origin)
/*
* End here
*/
[/java]

When the final return is made, the return value is the complete sequence of moves. This String object can then be printed to the console window, to a GUI Window or a file.

The Source Code

[java]
/**
* Determines the steps needed to move disks from an origin
* to a destination. The worstTme(n) is 0(2 raised to n),
* where n is the number of disks to be moved
*
* @param n the number of disks to be moved
* @param orig the pole where the disks are originally
* @param dest the destination pole
* @param temp the pole used for temporary storage
*
* @return a String representation of the moves needed
*
* @throws IllegalArgumentException if n is < = 0 */ public static String move(int n, char orig, char dest, char temp){ final String DIRECT_MOVE = "Move disk " + n + " from " + orig + " to " + dest + "\n"; if( n <= 0 ){ throw new IllegalArgumentException(); } if( n == 1 ){ return DIRECT_MOVE; } String result = move( n - 1, orig, temp, dest ); result += DIRECT_MOVE; result += move( n - 1, temp, dest, origin ); return result; } //end method move [/java]

In general, running the move method will return the complete sequence of moves needed to move disks from one pole to another. Earlier today, I did write the solution to this towers of hanoi puzzle on paper and here is how it looks like:

towers of hanoi

You can read more about the Towers of Hanoi game by clicking here

I hope you had fun reading through this post. If you have other ways of solving this problem, please share through the comments. Otherwise, please share this post using the buttons below and subscribe for more great stuff.

Be The First To Get New Posts From Simple Developer…

Written By Elisha Chirchir

Elisha Chirchir is a software developer. He is also the founder of Simple Developer and co-founder of Instinctive Software Solutions. On any given day, he works on both Android and Web Development. During his 'free time', he offers training to those interested in learning how to code in php, java, python, javaScript etc. You can easily find him on StackOverflow Android chatroom or on Twitter @Eenvincible

Leave a Reply

Your email address will not be published. Required fields are marked *