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 `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**

*<*>*: D1*<method getInt>*: U1, D2*<method hanoi>*: U1, D2*<method main>*: U1, D2*<method moveDisk>*: U1, D2