The solution to the Towers of Hanoi puzzle is a classic example of recursion. The ancient puzzle of the Towers Of Hanoi consists of a number of wooden disks mounted on three poles, which are in turn attached to a baseboard. The disks each have different diameters and a hole in the middle large enough for the poles to pass through. In the beginning, all the disks are on the left pole as shown in Figure 16.4.
Figure 16.4: The Towers of Hanoi
The object of the puzzle is to move all the disks over to the right pole, one at a time, so that they end up in the original order on that pole. You can use the middle pole as a temporary resting place for disks, but at no time is a larger disk to be on top of a smaller one. It's easy to solve the Towers of Hanoi with two or three disks, but the process becomes more difficult with four or more disks.
A simple strategy for solving the puzzle is as follows:
You can move a single disk directly.
You can move N disks in three general steps:
Move N-1 disks to the middle pole.
Move the last (Nth) disk directly over to the right pole.
Move the N-1 disks from the middle pole to the right pole.
The Visual Prolog program to solve the Towers Of Hanoi puzzle uses three predicates:
hanoi, with one parameter that indicates the total number of disks you are working with.
move, which describes the moving of N disks from one pole to another--using the remaining pole as a temporary resting place for disks.
inform, which displays what has happened to a particular disk.
/* Program ch16e05.pro */
DOMAINS
loc =right;middle;left