Project 4 Tower of Hanoi

Due: In the lab session of the week 12/09 - 12/13

Points: 30

Problem Statement:

The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks (The picture below just shows four disks for the interest of space), initially stacked in decreasing size on one of three pegs. The objective is to transfer the entire tower to one of the other pegs (the third one in the picture below), moving only one disk at a time and never a larger one onto a smaller.

Let’s call these 8 disks 1, 2, 3, 4, …, to 8, 8 being the largest disk and 1 being the smallest. Let’s call the pegs A, B, C. Design an algorithm to produce one solution for these 8 disks. Then output the sequence of disk movement. For instance, the correct movement sequence for 3 disks should be:

move disk 1 from peg A to peg C

move disk 2 from peg A to peg B

move disk 1 from peg C to peg B

move disk 3 from peg A to peg C

move disk 1 from peg B to peg A

move disk 2 from peg B to peg C

move disk 1 from peg A to peg C

Hints: Recursive solution

Let’s call the three pegs Src (Source), Aux (Auxiliary) and Dst (Destination). However one solves the problem, sooner or later the bottom disks will have to be moved from Src to Dst. At this point in time all the remaining disks will have to be on Aux. After moving the bottom disk from Src to Dst these disks will have to be moved from Aux to Dst. Therefore, for a given number N of disks, the problem appears to be solved if we know how to accomplish the following tasks:

  1. Move the top N-1 disks from Src to Aux (using Dst as an intermediary peg)
  2. Move the bottom disk from Src to Dst
  3. Move N-1 disks from Aux to Dst (using Src as an intermediary peg)

Grading policy

Note: If your program does NOT have a recursive function to solve the problem, instead, you only have a hard-coded output routine, you will get NEGATIVE grades for this project!

Achievements / Points Earned
A reasonable algorithm and an OK written program which may contain syntax errors / 10
A reasonable algorithm and the program can be assembled correctly / 15
A correctly working program which cannot output / 25
A correctly working program which produces the output in the right format / 30