Wednesday, April 9, 2014

Towers of Hanoi, Java implementation

Towers of Hanoi is a classic puzzle to move the discs of different sizes from one rod to another rod, in which the discs of larger sizes are never placed above the discs of smaller sizes.

The puzzle can be solved by a recursive or a non-recursive algorithms.

Recursive algorithm

The recursive algorithm is based on these actions:

Let the height of the origin peg be h,
1. Move h-1 discs from the origin peg to an open peg.
2. Move the h-th disc from the origin peg to the target peg.
3. Move the h-1 discs from the open peg to the target peg.

This algorithm reduces the problem from the peg(h) to the peg(h-1), peg(h-2) ....

The implementation is as follows: