In particular, you will write an assembly language program that
generates a tree-recursive process for solving a classic mathematical
recreation, the ``Towers of Hanoi'' puzzle. This puzzle has three
pegs, numbered as pegs 1, 2, and 3, and `n` disks, labeled as disk 1
through disk `n`. (The number `n` can vary; typical values might be in
the range from 1 to 8.) Disk 1 is smaller than disk 2, which is in
turn smaller than disk 3, and so forth, with disk `n` being the
largest. Initially all the disks are on peg 1, starting with disk `n`
on the bottom, disk `n`-1 on top of that, and so forth, up to disk 1
on the top. The goal is to move all the disks to peg 2. You may only
move one disk at a time: the top disk from any of the three pegs onto
the top of either of the other two pegs. Moreover, there is a
constraint: you must not place a larger disk on top of a smaller.

Your lab write up can be short and sweet, but it should be English. Specific details I will expect to see are the program you are asked to write, a description of how you tested your program (and/or test data and results) from the program. A few carefully chosen tests should be used to ensure all cases are covered and all likely bugs are exposed. Naturally, there is no reason to include any test which you haven't checked for correctness; that would just run (and not test) the program.

You will again use Xspim, as in lab 1.

The following is a Scheme version of the program you need to write; it
prompts for and reads in `n` and then prints out a list of the
necessary disk movements:

(define main (lambda () (display "Enter number of disks> ") (let ((n (read))) (hanoi n 1 2 3)))) (define hanoi ;move n smallest disks from start to finish using extra (lambda (n start finish extra) (if (= n 0) 'done (begin (hanoi (- n 1) start extra finish) (display "Move disk ") (display n) (display " from peg ") (display start) (display " to peg ") (display finish) (display ".") (newline) (hanoi (- n 1) extra finish start)))))

To get the strings displayed, see page A-48; the newline at the end of
each line can be accommodated by using a `\n`

(newline) character
at the end of the last string, i.e.:

.asciiz ".\n"would be the string to print out last, containing both the period and the newline.

As an alternative to the above Scheme version here is a C version. It
presumes that there are C library procedures
`print_string`

, `print_int`

, and
`read_int`

, corresponding with the SPIM system calls:

/* move n smallest disks from start to finish using extra */ void hanoi(int n, int start, int finish, int extra){ if(n != 0){ hanoi(n-1, start, extra, finish); print_string("Move disk "); print_int(n); print_string(" from peg "); print_int(start); print_string(" to peg "); print_int(finish); print_string(".\n"); hanoi(n-1, extra, finish, start); } } main(){ int n; print_string("Enter number of disks> "); n = read_int(); hanoi(n, 1, 2, 3); return 0; }

This lab is essentially exercise A.10.