CIT 591 Assignment 10: Jigsaw Puzzle
Fall 2011, David Matuszek

# Purposes of this assignment

• To get you started using multiple classes.
• To give you more experience with unit testing.

# General idea of the assignment

Create and solve a "jigsaw puzzle."

# Details

Each piece in a typical jigsaw puzzle has four edges (left, right, top, bottom) and can fit with other pieces in only one way. Since it's hard to represent curved edges in a program, we will use random numbers to represent edge shapes. Two edges will fit together if they have the same number. Hence, our completed jigsaw puzzle will look something like this:

 000 000 143 171
 000 143 777 091
 000 777 298 451
 000 298 000 380
 171 000 212 188
 091 212 317 167
 451 317 304 155
 380 304 000 441
 188 000 667 000
 167 667 850 000
 155 850 240 000
 441 240 000 000

All outside edges will be zero.

To simplify the problem, you never need to rotate pieces; the "top" side is always up.

Unit test these methods: `lastThreeDigits` and `toString` (in `PuzzlePiece`), `shuffle` (in `PuzzleCreator`), `findPiece` (in `PuzzleSolver`), and `isCorrectlyAssembled` (in `SolutionChecker`).

You should have the following classes. Each class should begin with a Javadoc comment telling the purpose of the class, and should have an `@author` tag. The main class (`JigsawPuzzle`) should have `@author` tags for both you and your partner.

## public class PuzzlePiece

This class describes a single piece of the puzzle. It holds four `private long` instance variables to describe the four sides of the puzzle piece.

```public PuzzlePiece(long top, long left, long right, long bottom)```

This is a constructor for puzzle pieces. For each of the four sides, it will do the following: If any parameter is exactly `-1`, it will choose a random `long` number for that side. If the parameter is any other number, it will use the parameter value for that side. (We can do this because, although it is possible for the random number generator to return `-1`, that will only happen about once every ten billion billion tries.)

Note: In order to avoid passing in -1 as a "magic number" (a number whose meaning is not obvious from context), give it a name in your class; define the varible `final long RANDOM = -1;`

```public long getTop() public long getLeft()```
`public long getRight()` ```public long getBottom()```
These "getter" methods return the values of `top`, `left`, `right`, and `bottom`, respectively. These methods allow other classes to find out the values of these variables, but make the variables `private` so that other classes cannot change those values. (You don't want people jamming in pieces where they don't really fit. ).
`public static int lastThreeDigits(longNumber)`
Returns, as an integer, the last three digits of the provided long number. Since the number could be negative, begin by taking its absolute value, then modding the result with 1000.

`public String toString()`
This returns a description of this puzzle piece, in the form `[top left right bottom]`. Long numbers are hard to read and compare because they have so many digits, so abbreviate" them with the `lastThreeDigits` method. This may give use some duplicate numbers, but we will only use this method when we want to print out pieces; we will use the original `long` numbers in fitting pieces togethe.
There are no methods that change the instance variables of the `PuzzlePiece` once it has been created. Do not add such methods to this class.

## public class JigsawPuzzle

This is the "main" class--that is, it holds the `main` method.

`public static void main(String[] args)`

Call the program with command-line arguments: `args[0]` as the number of rows, and `args[1]` as the number of columns. (In Eclipse: Run → Run Configurations... → Arguments → Program arguments:.) Print an error message and quit if you don't get exactly two command line arguments, or if they do not represent positive integers within a reasonable range.

Use the `PuzzleCreator` to create a puzzle. Save the puzzle as an instance variable, print it (as a list of puzzle pieces), then use the `PuzzleSolver` to solve the puzzle, use the `SolutionChecker` to ensure that the puzzle was solved correctly, and print the assembled puzzle.
`public void print(PuzzlePiece[][] puzzle)`

Prints the two-dimensional puzzle array. It should look something like this:

```+-----------+-----------+-----------+-----------+
|    000    |    000    |    000    |    000    |
|000     143|143     777|777     298|298     000|
|    171    |    091    |    451    |    380    |
+-----------+-----------+-----------+-----------+
|    171    |    091    |    451    |    380    |
|000     212|212     317|317     304|304     000|
|    188    |    167    |    155    |    441    |
+-----------+-----------+-----------+-----------+
|    188    |    167    |    155    |    441    |
|000     667|667     850|850     240|240     000|
|    000    |    000    |    000    |    000    |
+-----------+-----------+-----------+-----------+```
You can use `System.out.printf` with the` %03d` format to print numbers in the range 0 to 999, as shown above.

## public class PuzzleCreator

The `create` method in this class will need to generate unique (no two the same) random numbers, for use as edge "shapes." To do this, create a ```static Random``` random number generator and use its `nextLong()` method with no parameters.

`public PuzzlePiece[] create(int rows, int columns)`

This method creates the puzzle as a two-dimensional array, but then shuffles and returns it as a one-dimensional array. (If you didn't shuffle the pieces, it wouldn't be much of a puzzle, would it?)

`public static void shuffle(Object[] objects)`

Randomizes a one-dimensional array. It is easy to write a method that produces results that "look random;" it is more difficult to write a method that does not bias the results in some subtle way. Here is a provably correct method:

```for N from the array length down to 1:
choose a random number R, where 0 <= R < N
swap array locations N and R
```
("Down to" means step by `-1`.) Note that it is not worth checking whether you are swapping a location with itself (`N == R`), because this doesn't happen often and it does no harm when it does happen.

## public class PuzzleSolver

```public PuzzlePiece[][] solve(int rows, int columns, PuzzlePiece[] pieces)```

Given the one dimensional array of PuzzlePieces, and the number of rows and columns the result should have, assembles the puzzle by creating a two-dimensional array of the right size, and placing all the pieces into it. (Hint: Find the piece that goes in `[0][0]` and put it there; then work across and down, finding each piece as needed.).

```PuzzlePiece findPiece(long topWanted, long leftWanted, PuzzlePiece[] pieces)```

Searches the one-dimensional array of pieces for a piece whose `top` edge is `topWanted` and whose `left` edge is `leftWanted`. This method can be used by the `solve` method.

If a piece cannot be found, the method should create and throw a `RuntimeException(message)`. The message should include information about the piece being searched for. Of course, if the `PuzzleCreator` did its job properly, this should never happen.

## public class SolutionChecker

```public boolean isCorrectlyAssembled(PuzzlePiece[][] solution)```

Checks the completed puzzle (the two-dimensional array) to make sure that all the pieces in it have been placed correctly. Edge pieces should have a zero value for their outside edge(s); pieces that are adjacent to other pieces should have the same numbers for their touching edges (top against bottom, left against right). Returns `true` if all pieces "fit together", `false` otherwise.

Note that, if your program works correctly, `isCorrectlyAssembled()` should always return `true`.

# Partners

If you are unable to work closely with your partner, one of you should write the `JigsawPuzzle` and `PuzzleSolver` classes, while the other should write the `PuzzleCreator` and `SolutionChecker` classes. In this case you may need to create some "fake data" for testing purposes.

# Structure of the assignment

• Project name: `JigsawPuzzle`
• Package name: `jigsaw`
• Class names and method signatures: As above.
• Provide Javadoc documentation for all classes and methods

# Due Date

Before 6am, December 2. Zip your entire project and submit via Sakai. As this is a pair programming assignment, only one of you should submit the assignment, with both your names prominently displayed, as described above. As always, only assignments submitted via Sakai will be accepted--do not send your program by email. A late penalty of 5 points per day (out of 100 points) will apply.