Towers of Hanoi
The 'Towers of Hanoi' is a classical =
problem used to=20
illustrate the power of recursion. The puzzle goes as =
follows.=20
There are three poles and 64 discs of =
different=20
sizes. Initially, all the discs are placed on the first pole =
with=20
the largest disc at the bottom and the smallest one at the =
top. We=20
need to move all the discs from the first pole to the third =
pole,=20
with the smallest disc at the top and the largest at the =
bottom. We=20
can move only one disc at a time (which should be the =
topmost disc)=20
and at any point of time, a larger disc cannot be placed =
over a=20
smaller one i.e. all the discs on a pole must be placed in =
such a=20
way that the smallest is at the top and the largest at the =
bottom.=20
The second pole can be used as an intermediate pole to help =
us in=20
transferring the discs.
This puzzle can be solved using recursion. =
For a=20
moment, assume that there are just two discs (disc 1 and 2; =
disc 2=20
being the larger one) on the first pole. The solution =
consists of=20
three steps.
Step 1: Move disc 1 from pole 1 to pole =
2.
Step=20
2: Move disc 2 from pole 1 to pole 3.
Step 3: Move disc 1 =
from=20
pole 1 to pole 3.
Now, assume that disc 1 is not a single =
disc but a=20
collection of discs. The procedure would be similar to the =
above=20
three steps, but steps 1 and 3 would be a collection of =
steps. Step=20
1 would be to move the n-1 discs (assuming that there were a =
total=20
of n discs) from pole 1 to pole 2. For moving these (n -1) =
discs, we=20
again follow the same strategy of considering them as 1 disc =
plus a=20
set of n-2 discs. Step 3 would also be similar. This gives =
us the=20
recursive solution.
Recursive Algorithm
The recursive solution to move n discs =
from the=20
start pole to the end pole using an auxiliary pole is given =
below.=20
Base Case - When n =3D 1
Move the disc =
from start=20
pole to end pole
Recursive Case - When n > 1
Step 1: =
Move (n-1)=20
discs from start pole to auxiliary pole.
Step 2: Move the =
last=20
disc from start pole to end pole.
Step 3: Move the (n-1) =
discs=20
from auxiliary pole to end pole.
Steps 1 and 3 are =
recursive=20
invocations of the same procedure.
Java Program
The recursive program for the puzzle in =
Java is=20
given below:
public class TowersOfHanoi {
=
=20
public void solve(int n, String start, String =
auxiliary,=20
String end) {
if (n =3D=3D 1) =
{
=20
=
System.out.println(start +=20
" -> " + end);
} else =
{
=20
solve(n - 1, start, end,=20
auxiliary);
=20
System.out.println(start + " -> " + end);
=
=20
solve(n - 1, auxiliary, start, =
end);
=20
}
}
=
=20
public static void main(String[] args) {
=
=20
TowersOfHanoi towersOfHanoi =3D new =
TowersOfHanoi();
=20
System.out.print("Enter number of =
discs:=20
");
Scanner scanner =3D new=20
Scanner(System.in);
int discs =
=3D=20
scanner.nextInt();
=20
towersOfHanoi.solve(discs, "A", "B", "C");
=20
}
}
The method solve() takes four arguments :=20
n - the number of discs in the =
puzzle
start,=20
auxiliary, end -the names of the three poles which will be =
used for=20
printing the solution
We first check if the number of poles, n =
is equal to=20
one. If so, the base case solution will be used which =
consists of=20
moving a disc from the start peg to the end peg. If not, the =
recursive solution is used which consists of two recursive =
calls to=20
the same procedure solve(). When we need to move n-1 discs =
from the=20
start pole to the auxiliary pole, the auxiliary pole becomes =
the end=20
pole and the end pole becomes the auxiliary pole. That is =
why we=20
have written
solve(n - 1, start, end, =
auxiliary)
instead=20
of
solve(n - 1, start, auxiliary,=20
end)
Next we print ' start -> end ' which =
corresponds=20
to moving the largest disc at the bottom from the start peg =
to the=20
end peg.
Finally, we have recursive invocation of =
solve().=20
Here, the auxiliary peg becomes the start peg and the start =
peg=20
becomes the auxiliary peg.
Here is a sample output with n =3D 3. =
Enter number of discs: 3
A -> C
A =
->=20
B
C -> B
A -> C
B -> A
B -> C
A =
->=20
C
|
![3D""](3D"https://fbcdn-profile-a.akamaihd.net/hprofile-ak-xpa1/v/t1.0-1/c12=)
![](3D"https://fbcdn-profile-a.akamaihd.net/hprofile-ak-xaf1/v/t1.0-1/p50=)
![](3D"https://fbcdn-profile-a.akamaihd.net/hprofile-ak-xap1/v/t1.0-1/p50=)