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