Towers of Hanoi
This program uses a recursive function to output the moves necessary to solve the "Towers of Hanoi" ancient Chinese puzzle, and is a favourite exercise for C instructors.
For those unfamiliar with the puzzle, it involves having three columns on which are placed a number of different sized disks. Originally, there was a stack of 64 disks on one column in order of size (the biggest disk on the bottom of the column, the smallest disk on the top). The ancient Chinese monks reputedly had to move the entire stack from that column to another column, with the following restrictions:
- Only one disk can be moved at a time
- A disk can only be moved onto an empty column, or on top of a larger disk
A Java version of this puzzle is also available.
Programming Issues
This is a problem for which recursion is ideal. Beginners are often surprised at how simple the algorithm is, and how little it appears to do.
To demonstrate how the algorithm works, let us suppose we wish to move 5 disks from column 1 to column 3. The steps are as follows:
- Move 4 disks from column 1 to column 2
- Move 1 disk from column 1 to column 3
- Move 4 disks from column 2 to column 3
In other words, to move n disks from one column to another, move n-1 disks to the "spare" column, move the nth disk to the destination column, and finally move the n-1 disks from the "spare" column back on top of the nth disk. Recursion then takes care of moving the n-1 disks by using the same algorithm until we have no more disks left to move.
The program has been complicated slightly more than necessary by adding a command line interface to set the parameters.
Usage
Issue the following command line:
hanoi -d4 -s1 -e3
where:
-d{n}specifies the number of disks to move-s{n}specifies the column to move from (must be 1, 2 or 3)-e{n}specifies the column to move to (must be 1, 2 or 3 and different to the start column)