A Simple Recursive Solution
to the “Towers of Hanoi” problem
Java implementation by Apostolos Syropoulos

This program implements the “classical” recursive algorithm that solves the Towers of Hanoi problem. The recursive algorithm is based on the observation that moving a tower of height h from pole A to pole B is equivalent to moving a tower of height h-1 to pole C, them moving the last disk from pole A to pole B, and finally moving the the tower from pole C to B. So the problem of moving a tower of height h, has been reduced to the one of moving a tower of height h-1.

The following Java application uses only one class variable, moves, which holds the number of moves so far. The variable is used only for formating purposes.

<*>= import java.io.*; public class hanoiA { static int moves=0; //number of moves so far <method getInt> <method hanoi> <method moveDisk> <method main> }

This code is written to a file (or else not used).

Method getInt is used to read an integer from the user terminal. The method is based on the new API therefore the whole program cannot be executed with an old JDK. Its functionality is very simple: it reads an input line which is supposed to contain only one integer. If the line contains what should contain it transforms the line into a valid integer and return it, otherwise it returns the number 1 and print an error message.

<method getInt>= static int getInt() { String line; BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); try { line = in.readLine(); int i = Integer.valueOf(line).intValue(); return i; } catch (Exception e) { System.err.println("***Error: Input is not a number.\n" + "Input assumed to be the number 1"); return 1; } }

Used above.

Method hanoi is the kernel of the program---it “performs” the moves. It accepts four arguments: the height of the current tower, the fromPole, the toPole and the withPole. Initially the tower has height, say n. Then we must move a tower of height n-1 from fromPole to withPole, move the biggest disk from fromPole to toPole and finally move the tower of height n-1 to pole toPole from withPole. The first step is implemented as a call to the method itself (procedures are called methods in Java), the second to a call to method moveDisk, and finally the third step to a call to the itself. Particularly, the withPole is the pole we move the tower of height n-1.

Each recursive method must have a termination condition, i.e., a condition that signals the termination of the method, or else it will never terminate! In our case this condition is reached when the height of the tower is zero.

<method hanoi>= static void hanoi(int height, char fromPole, char toPole, char withPole) { if (height >= 1) { hanoi(height-1, fromPole, withPole, toPole); moveDisk(fromPole, toPole); hanoi(height-1, withPole, toPole, fromPole); } }

Used above.

Method moveDisk simply print on the terminal each move. A “move” is defined by the orientation pole and the destination pole, each represented by a character. The method prints a string of the form “FT” where “F” denotes the orientation pole and “T” the destination pole. Moreover, it tries to make the output readable. So, it prints only twenty moves per line, by detecting multiples of the number 20.

<method moveDisk>= static void moveDisk(char fromPole, char toPole) { moves++; System.out.print(fromPole); System.out.print(toPole); System.out.print(((moves % 20)==0) ? '\n' : ' '); }

Used above.

Method main is there where the whole action is. The first thing is to define the poles as characters and to the height of the tower as an integer. Next, it reads the height of the tower (in case we type some rubbish or a negative number, the height is assumed equal to 1). Finally, it prints out the solution. The last aspect of this program is that it print its execution time in milliseconds.

<method main>= public static void main(String[] args) { long time1, time2; //for benchmarking int TowerHeight; char FromPole='A', ToPole='B', WithPole='C'; System.out.println("Enter Tower height..."); System.out.print("?"); TowerHeight = getInt(); time1 = System.currentTimeMillis(); hanoi(TowerHeight, FromPole, ToPole, WithPole); time2 = System.currentTimeMillis(); System.out.println(); System.out.print(time2-time1); //print execution time in msec System.out.println(" msec execution time"); }

Used above.

*Back to the main page
Get the source code
Code Chunk Index