2.3 Towers of Hanoi puzzle

This object of this famous puzzle is to move N disks from the left peg to the right peg using the center peg as an auxiliary holding peg. At no time can a larger disk be placed upon a smaller disk. The following diagram depicts the starting setup for N=3 disks.

Fig. 2.3
Fig. 2.3

Here is a recursive Prolog program that solves the puzzle. It consists of two clauses. 

move(1,X,Y,_) :-  
    write('Move top disk from '), 
    write(X), 
    write(' to '), 
    write(Y), 
    nl. 
move(N,X,Y,Z) :- 
    N>1, 
    M is N-1, 
    move(M,X,Z,Y), 
    move(1,X,Y,_), 
    move(M,Z,Y,X).
The variables filled in by '_' (or any variables beginning with underscore) are 'don't-care' variables. Prolog allows these variables to freely match any structure, but no variable binding results from this gratuitous matching.

Here is what happens when Prolog solves the case N=3. 

?-  move(3,left,right,center). 
Move top disk from left to right 
Move top disk from left to center 
Move top disk from right to center 
Move top disk from left to right 
Move top disk from center to left 
Move top disk from center to right 
Move top disk from left to right 
 
yes

The first clause in the program describes the move of a single disk. The second clause declares how a solution could be obtained, recursively. For example, a declarative reading of the second clause for N=3, X=left, Y=right, and Z=center amounts to the following:

move(3,left,right,center) if
move(2,left,center,right) and ] *
move(1,left,right,center) and
move(2,center,right,left). ] **
This declarative reading of the clause is obviously correct. The procedural reading is closely related to the declarative interpretation of the recursive clause. The procedural interpretation would go something like this:
In order to satisfy the goal ?- move(3,left,right,center) do this :
satisfy the goal ?-move(2,left,center,right), and then
satisfy the goal ?-move(1,left,right,center), and then
satisfy the goal ?-move(2,center,right,left).
Also, we could write the declarative readings for N=2:
move(2,left,center,right) if ] *
move(1,left,right,center) and
move(1,left,center,right) and
move(1,right,center,left).

move(2,center,right,left) if ] **

move(1,center,left,right) and
move(1,center,right,left) and
move(1,left,right,center).
Now substitute the bodies of these last two implications for the heads and one can "see" the solution that the prolog goal generates.
move(3,left,right,center) if
move(1,left,right,center) and
move(1,left,center,right) and *
move(1,right,center,left) and
---------------------------
move(1,left,right,center) and
---------------------------
move(1,center,left,right) and
move(1,center,right,left) and **
move(1,left,right,center).
A procedural reading for this last big implication should be obvious. This example illustrates well three major operations of Prolog:
1) Goals are matched against the head of a rule, and

2) the body of the rule (with variables appropriately bound) becomes a new sequence of goals, repeatedly,

until

3) some base goal or condition is satisfied, or some simple action is taken (like printing something).

The variable matching process is called unification.

Exercise 2.3.1 Draw a program clause tree for the goal 'move(3,left,right,center)' show that it is a consequence of the program. How is this clause tree related to the substitution process explained above?

Exercise 2.3.2 Try the Prolog goal ?-move(3,left,right,left). What's wrong? Suggest a way to fix this and follow through to see that the fix works.

Prolog Code for this section.
Prolog Tutorial Contents