solution

 

We have presented details about the Towers of Hanoi puzzle in Exercise 11-P16 on page 469. Write a recursive procedure in the MIPS assembly language to solve this puzzle. Also, write a simple main program to test your program.

 

Exercise 11-P16

 

Write a program to solve the Towers of Hanoi puzzle. The puzzle consists of three pegs and N disks. Disk 1 is smaller than disk 2, which is smaller than disk 3, and so on. Disk N is the largest. Initially, all N disks are on peg 1 such that the largest disk is at the bottom and the smallest at the top (i.e., in the order N, N ̶ 1, … , 3, 2, 1 from bottom to top). The problem is to move these N disks from peg 1 to peg 2 under two constraints: You can move only one disk at a time and you must not place a larger disk on top of a smaller one. We can express a solution to this problem by using recursion. The function

moves N disks from peg 1 to peg 2 using peg 3 as the extra peg. There is a simple solution if you concentrate on moving the bottom disk on peg 1. The task move (N, 1, 2, 3) is equivalent to

 

 

Even though the task appears to be complex, we write a very elegant and simple solution to solve this puzzle. Here is a version in C.

Test your program for a very small number of disks (say, less than 6). Even for 64 disks, it takes hundreds of thousands of years on whatever PC you have!