CSU380 Lab 5 - Spring, 2009

Adapted from: CS61C, UCBerkeley

Towers of Hanoi

Purpose:

Further practice in writing MIPS programs and a review of recursion. Introduction: The Tower of Hanoi is an ancient puzzle involving three pegs, and an arbitrary number of circular discs, each of a different size, and with holes in their centers for the pegs to fit through: 
        __|__               |                 | 
       |_____|              |                 |    
      ____|____             |                 |  
     |_________|            |                 |
   _______|________         |                 |
  |_______________|         |                 |
          |                 |                 |
  ________|_________________|_________________|______________
         PEG1              PEG2              PEG3
The puzzle is begun by placing all of the discs on one of the pegs, from largest on the bottom to smallest on the top (see diagram above). The goal is to move all of the discs to another peg, following these simple rules: 
        ____|____
   |_________|
      __|__     WRONG!
     |_____|
        |
________|________
 Assignment: Your task is to write a piece of MIPS code that will print instructions on how to move from PEG1 to either PEG2 or PEG3, step by step, for an arbitrary number of discs. You may assume that all of the discs begin on PEG1.

Here is a C version of the solution to the puzzle: 

/* This program provides the solution to the */
/* Towers of Hanoi problem written in C. */

#include <stdio.h>

static char peg1[] = "one";
static char peg2[] = "two";
static char peg3[] = "three";

void Hanoi(char * source, char * spare, char * destination, int n)

/* This function takes a tower of n discs and prints */
/* instructions for moving from peg 'source' to peg */
/* 'destination'. Peg 'spare' may be used temporarily. */

{
  if (n>0)
   {
     Hanoi(source, destination, spare, n-1); /* recursive call */
     printf("Move disk from %s to %s\n", 
                    source, destination); /* move one disk */
     Hanoi(spare, source, destination, n-1); /* recursive call */
   }
}

main()
{
  int n;

  printf("Please enter the number of disks: ");
  scanf("%d",&n);
  printf("\n");
  Hanoi(peg1,peg2,peg3,n);
}

Prelab:

Study the C version of the Hanoi program - make certain you understand how it works.  Think about how you would rewrite the function "Hanoi" in MIPS assembly language, then write on paper or in a file a preliminary version.  Assume that there is a procedure provided to for printing moves.

Task 1: Create a "lab" directory and copy the lab file: "/course/csu380jc/.www/lab5/lab5.s".

Task 2: Study the "main:" procedure, figure out how it operates. It is currently set so that 4 discs begins on the first peg.  For checkoff you will have to start with 5 discs.

Task 3: Go to the "hanoi:" procedure and fill in the prologue and epilogue, plus anything else you need, using the MIPS version that you developed in the prelab.  The procedure "hanoi" receives the source peg in $a0, "spare" peg in $a1, destination peg in $a2, and number of discs (n) in $a3.

Your routine will call "print_message" for printing moves.

Your program should work for any arbitrary non-negative number of starting disks, i.e. your program must work for n=0 but not n=-1. Sample Output:

Here is sample output for n=4 discs:

Move disk from one to two
Move disk from one to three
Move disk from two to three
Move disk from one to two
Move disk from three to one
Move disk from three to two
Move disk from one to two
Move disk from one to three
Move disk from two to three
Move disk from two to one
Move disk from three to one
Move disk from two to three
Move disk from one to two
Move disk from one to three
Move disk from two to three

For Checkoff:

Show me your MIPS code and run your program for n=5 discs.
This page last modified 2/20/2008.