Towers of Hanoi

Objectives

  1. Create a last-in-first-out (LIFO) data structure.

  2. Write a program that will solve the Towers of Hanoi.

  3. Solve the problem using both recursion and iteration.

  4. Use stack data structures more extensively.

Acknowledgement

This assignment was heavily copied from the wonderfully competent faculty at Princeton University. Permission to use the assignment was granted via email by Dr. Robert Sedgewick. We gratefully acknowledge the material from Princeton University used in this assignment! The original Princeton assignment is here.

Copyright © 2000–2011, Robert Sedgewick and Kevin Wayne.

Getting Started

  1. Create a new Java project called P5 and import TowersOfHanoi-starter.jar.

Your directory should look like this:

P5/
├── resources
│   └── Towers.jpg
└── src
    ├── MyStack.java
    ├── MyStackTestProgram.java
    ├── UserInterface.java
    ├── TowersOfHanoi.java
    └── StdDraw.java
Description

There are two parts to this assignment.

  • The first part is gaining a better understanding of how stacks work.

  • The second part is to understand how to implement the Towers of Hanoi algorithm.

Part One - Building a Stack

You will be using a generic ArrayList to create a stack and using the MyStackTestProgram class to test your implementation. The last index of the ArrayList is the top of the stack.

Note
 You may use any method in ArrayList except contains, indexOf, and lastIndexOf.

  • Open the MyStack class.

  • Declare a private field of type ArrayList<E>

  • Implement each method using the javadoc.

    • Start by implementing the toString() method since all of the tests in the MyStackTestProgram class depend on this method being correct.

  • Remember to incrementally develop. Test one method at a time.

Warning
 Your implementation of MyStack.java MUST pass all testing in order to use it for this assignment.
Part Two - Implementing Towers of Hanoi

  1. Add code to the main method to initialize the puzzle by pushing all the discs onto the left stack, in descending order. Run the program with the command line arguments "10 -recursive" and you should see the picture shown below.

Towers

  1. Use the specifications in the javadoc to implement the recursive method.

  2. Use the specifications in the javadoc to implement the Move class.

  3. Use the specifications in the javadoc to implement the iterative version

Specifications

Your program must meet the following specifications:

  • The code must produce the correct upload file and assertion messages.

  • Work on your own, as always.

  • You must submit TowersOfHanoi.java with the recursive and iterative solutions.

  • Assignments should be implemented using Java 1.8.

  • Make sure your code runs on machines in the COMCS 120 lab.

  • Submit your program to the Checkin tab as you were shown in the recitation.

  • Read the syllabus for the late policy.

  • We will be checking programs for plagiarism, so please don’t copy from anyone else.

  • Assignments will be checked to make sure you implemented both recursive and iterative solutions.

Grading Criteria

  • 100 points for perfect submission.

  • 0 points for no submission, will not compile, submitted class file, etc.

  • Preliminary Tests:

    • testCompile: Checks compilation. (0 points)

    • testRecursive2: Checks recursive Tower of Hanoi solution, with 2 discs. (20 points)

    • testRecursive3: Checks recursive Tower of Hanoi solution, with 3 discs. (20 points)

    • testRecursive4: Checks recursive Tower of Hanoi solution, with 4 discs. (20 points)

    • testIterative: Checks iterative Tower of Hanoi solution, with 6 discs. (Extra Credit: 10 points)

  • Final Tests are identical to the preliminary tests, but with more discs.

    • testRecursive5: Checks recursive Tower of Hanoi solution, with 5 discs. (20 points)

    • testRecursive6: Checks recursive Tower of Hanoi solution, with 6 discs. (20 points)

Important
 Submit TowersOfHanoi.java to Checkin