The solution to the Towers of Hanoi problem given in the text assumes that the pegs are numbered, and the complete description is in those terms. Thus 1 3 is interpreted as move the (top) ring from peg 1 to (become the top ring of) peg 3. An alternative view is to assume that the n·ngs are numbered from the smallest to the largest starting at 1. We can then describe moves by indicating the ring to be moved and its direction. For convenience we will describe the directions as clockwise (C), and anticlockwise (A ), thinking of the towers as being in a triangular formation with the pegs numbered anticlockwise. Thus the following are two alternative descrip tions of moving a tower for n=3.
13 IC
12 2A
32 IC
13 3C
21 IC
23 2A
1 3 IC
Write a procedure to produce the alternative description of the moves based on the observations:
(i) If we can move a tower of k rings in either direction we can certainly move a tower of k +1rings by:
(a) moving the top k rings in the opposite direction ;
(b) moving ring k +1 in the correct direction ;
(c) moving the top k rings again in the opposite direction.
(ii) We can trivially move one ring.