Assignment 8 - The Towers of Hanoi

1. Downloading
   Download this page onto your computer and place it on your webpage using

          wget http://www.comp.nus.edu.sg/~gem1501/assignment08.html 

   Look with an editor at the file.
   While editing you can write out the file and use the refresh-button to see the results of your changes.


2. Implement the algorithm from the lecture
   Modify the lines with the moves. Replace them by a structure of recursively called functions which move the towers from position "towera" to position "towerb" using position "towerc". The variable "quantity" says how many pegs are moved. Refer to page 31 in Harel's book for details of the algorithm. The function can call itself if quantity > 1.

The frame "movetop" is already there. Movetop should be called in the main program such that towera is set to 0 and towerb to 1. The numbers used for the pegs are 0,1,2 (in the case of 3 pegs).

3. Change Parameters
   Increase the value for the parameter rings to 7 and to 10 and run the program with each of these parameters. How many moves are made? Then set rings to 10, pegs to 4 and replace the main call of "movetop" by the sequence

          movetop(5,0,2,3);
          movetop(5,0,1,3);
          movetop(5,2,1,3); 

   How many moves are now made? Note that for changing the values of rings and pegs, you have to edit the program at that place where the initial values are assigned at "var rings = 6;" and "var pegs = 3;".


4. Towers of Hanoi with 5 Pegs
   Using 5 pegs gives even more advantage than using 4 pegs. The task is to find a method with less than 40 moves for 5 pegs and 10 rings, here the pegs have the names 0,1,2,3,4. The best known method found for this assignments so far is 31 moves. If you solve this talk, you can hand it in by showing it to the lecturer during the laboratory sessions.