The Towers of Hanoi is a classic puzzle in computer science whose solution is not obvious. Imagine three poles and a number of disks of varying diameters. Each disk has a hole in its center so that it can fit over each of the poles. Suppose that the disks have been placed on the first pole in order from largest to smallest, with the smallest disk on top. Here is the initial configuration for three disks:
The goal is to move the entire stack of disks to either of the others so that they remain piled in their original order. You can move only one disk—the topmost one—at a time from one pole to another, and disks can only be stacked on top of larger disks. You can store disks on another pole temporarily, as long as you observe the previous restrictions.
If we label the poles A, B, and C and place n disks on pole A, a recursive algorithm will move the disks to
pole C, as follows:
if (n == 1)
Move the disk from pole A to pole C
else
{
Move n - 1 disks from pole A to pole B, leaving the largest disk alone on pole A
Move the disk from pole A to pole C
Move n - 1 disks from pole B to pole C
}
Implement a recursive solution to the Towers of Hanoi puzzle. Your program should display a list of the moves necessary to solve the puzzle. For example, if three disks are on pole A, the following sequence of seven moves will move the disks to pole C, using pole B temporarily:
Move a disk from pole A to pole C
Move a disk from pole A to pole B
Move a disk from pole C to pole B
Move a disk from pole A to pole C
Move a disk from pole B to pole A
Move a disk from pole B to pole C
Move a disk from pole A to pole C
Use a value of 3 for n while you are developing your solution. Test your program with values of n up to 9.