Homework 2

Post date: Jul 2, 2009 6:37:55 PM

Administrative

Deadlines:

    • With a 10% bonus: Friday, July 10, 2009, at 11:59pm.
    • Last deadline: Monday, July 13, 2009, at 11:59pm.
    • No late submission will be accepted.

All students must adhere to Academic Code of Conduct. You are welcome to brainstorm ideas with your fellow students, but you are not allowed to share code.

Description

By now, you should be familiar with basic Eclipse features and running unit tests. In this homework, there are two parts. In the first part, you will manipulate singly and doubly linked lists. In the second part, you will write the Naname solver (based on your code in the previous assignment) and write some unit tests for it. The solver will involve writing recursive functions. Again, use the provided code hw2.zip, which is attached below.

Here is a quick rundown of a list of functions you need to implement or functions of interest. The provided functions may help you with the functions you need to implement, so you should study them.

    • SinglyLinkedList.java
      • (provided) public int Length()
      • (10 pts) public void Append(T item)
      • (provided) public T Nth(int n)
      • (10 pts) public void Insert(T item, int n)
      • (20 pts) public void Reverse()
    • SinglyLinkedListTest.java
      • (provided) public void testAppend()
      • (10 pts) public void testNth()
    • DoublyLinkedList.java
      • (30 pts) public void Reverse()
    • DoublyLinkedListTest.java
      • (10 pts) public void AssertDoubleLinks() (explain what it does)
    • Naname.java
      • (10 pts) modify your Naname class from hw1 to make it implement the Puzzle interface.
    • PuzzleSolver.java
      • (provided) interface Puzzle
      • (50 pts) public boolean Solve()
    • PuzzleSolverTest.java
      • (provided) public void testSolveCheckerBoard()
      • (10 pts) public void testSolveAltRows()
      • (10 pts) public void testSolveAltColumns()
      • (10 pts) public void testSolveAltRowsColumns()
    • Sudoku.java
      • (20 pts extra credit) If you want to see that your puzzle solver also works with Sudoku, create a Sudoku class that implements the Puzzle interface, then modify NanameSolverMain to solve for Sudoku puzzles using the same PuzzleSolver you wrote.

For a total of 180 points + 20 extra credit.

If you cannot finish this homework, try to concentrate on what you do know how to do. Try not to work on many incomplete functions for partial credit.

Additional Instructions for the Puzzle Solver

In the last homework, you implemented the Naname class. In particular, there is one method Tally() that gives you the occurrence of each number values 0 (UNDECIDED) and 1 through 9, covered by the "uniqueness domain." For Naname, the uniqueness domain is the diagonal, anti-diagonal, and the sub-block that contains the specific row-column position. For Sudoku, it is the row, column, and the sub-block. You notice that the rules of Naname and Sudoku are similar enough that you can write one solver for both! The solver would use Tally() and only try the number values 1 through 9 that has zero occurrence in the "uniqueness domain." You don't need to try anything else.

In order to write one solver for both Naname and Sudoku, suppose you worked out the "common" interface between them that describes what these puzzle games must implement in common, and you called the interface Puzzle. The Puzzle interface can be found in the PuzzleSolver.java file; please read over it.

Your first step is to copy Naname.java from hw1 and modify it to implement this interface. In order to do that, you need to modify the class line to read:

public class Naname implements Puzzle { ... }

And then try to work out the discrepencies between what your class provides and what the interface expects. This should be pretty easy.

After you complete this step, the red X next to NanameSolverMain.java and PuzzleSolverTest.java should disappear, as they can now reference the class.

Once you finish PuzzleSolver, select NanameSolverMain.java and click on the Run button. A file dialog will pop up and allow you to choose a text file that contains a partial puzzle. Some solvable and non-solvable puzzles are provided in the examples folder. For each solution found, the completed puzzle is printed to console, and at the end a message box will pop up indicating whether the puzzle can be solved.

Solving some puzzles can take a very long time, but the examples provided should finish running in a minute or two.