CIT 591 Assignment 4: Jigsaw Puzzles (revised) Fall 2004, David Matuszek

I have made minor revisions in this assignment (in blue), mostly to clarify what should be printed, and where it should be printed from.

Purposes of this assignment:

• To give you more experience with arrays, classes, and methods.

General idea of the assignment:

Create a "jigsaw puzzle," disassemble it (break it up into pieces and shuffle the pieces), then reassemble it.

This program is to be done with a partner, if possible. Partners will be assigned.

There are two classes, but one of them (`PuzzlePiece`) is very simple; whoever does this part should also write some of the `Puzzle` methods. The most difficult methods are the `Puzzle` constructor, `solve()`, and `isCorrectlyAssembled()`.

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:

 0 0 1 143 17
 0 143 2 777 191
 0 777 3 298 451
 0 298 4 0 380
 17 0 5 212 188
 191 212 6 317 167
 451 317 7 304 155
 380 304 8 0 441
 188 0 9 667 0
 167 667 10 850 0
 155 850 11 240 0
 441 240 12 0 0

All outside edges will be zero.

Here I have numbered the pieces (in blue). The piece numbers should not be used in assembling the puzzle, but only for printing out the assembled puzzle and checking to see whether the puzzle was put together correctly.

Use `long` random numbers for the edges. There is a method in the `Random` class called `nextLong()` that is used just like `nextInt()`. If you create a single instance of `Random`, it is programmed in such a way that you will never get the same number twice, so you don't have to worry about having duplicate edges.

To simplify the problem somewhat, you never need to rotate pieces; you always know which edge is up.

You should have these classes:

`PuzzlePiece`

This class describes a single piece of the puzzle. It holds five `private` instance variables: An `int` that represents the piece number (in blue above), and four `long`s to describe the four sides of the puzzle piece. The class itself will hold a `private static int id` (initially zero) used to number by the constructor to number the pieces.

```public PuzzlePiece(long top, long left, long right, long bottom) ```
This is a constructor for puzzle pieces. When you construct a puzzle piece, you must supply values for all four sides.

The constructor should also assign a piece number to the piece, as follows: Add `1` to the static variable `id`, then use the result as the piece number. (For this to work, it is essential that the `id` variable be `static`!)

Each time you create a piece, print a message of the form ```Created piece 3: [0 12 552 -291]```. Use the piece's `describe()` method to get the piece description to be printed.

``` 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 (because the variables are `private`), other classes cannot change those values.

` ``public String toString()`

This returns the `id` of this puzzle piece, as a three-character right-justified `String`. That is, `"  5"` and `" 25"` instead of just` "5"` or `"25"`. You can assume that you will have fewer than 1000 puzzle pieces, so three digits will always be enough. This method prepares a string for printing, but it does not itself print anything.

`public String describe()`

This returns a "long description" of this puzzle piece, in the form `number: [top left right bottom]`, where (for readibility) the edge numbers have been reduced to three or fewer digits by dividing by `10000000000000000L`. For example, return `(top/10000000000000000L)` as part of the output string instead of `top`, and similarly for the other sides. The returned string should look something like: `3: [0 12 552 -291]`. This method prepares a string for printing, but it does not itself print anything.
There are no methods that change the instance variables of the `PuzzlePiece` once it has been created. Do not add any additional methods to this class.

`Puzzle`

This class describes the entire puzzle. It contains two arrays: A one-dimensional array of `PuzzlePiece` used to hold all the puzzle pieces when the puzzle is not assembled, and a two-dimensional array of `PuzzlePiece` to hold the assembled pieces.

`public Puzzle(int rows, int columns)`

This constructor is fairly complex. It does the following:

1. Prints a message that says it is about to create a jigsaw puzzle, and tells the number of rows and columns in the puzzle.

2. Creates the necessary one- and two-dimensional arrays. All elements of these arrays will initially be null.

3. Creates all the puzzle pieces and assemble them into a completed puzzle in the two-dimensional array. This is so that you can create pieces that fit with other pieces in a specific array location--you have to look at what pieces have already been placed adjacent to the new piece, and use their adjacent edge values (and some new ones) when creating each new piece. Each time you add a piece, this constructor prints out a long description of the piece (use its `describe()` method) and the partially completed puzzle (using this class's `print()` method)

(Note: The `solve` method does something quite different, so we can't just call it to do this for us.)

4. Once the puzzle has been created in an assembled form, disassembles it. Use the `disassemble()` method to do this.

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

Constructs a `Puzzle` and calls its `doPuzzle()` method. The number of rows and columns in the puzzle should be taken from `args[0]` and `args[1]`, respectively.

`public void doPuzzle()`

1. Calls `print()` to print the (unassembled) puzzle and the array of puzzle pieces.
2. Calls` solve(0)` to assemble the puzzle.
3. When the puzzle has been completed, calls `isCorrectlyAssembled()`, and prints a victory message (or possibly an error message).

`public void disassemble()`

Copies (the reference to) each piece from the two-dimensional array into the one-dimensional array, "nulls out" the two-dimensional array (sets all locations to `null`), then calls `shuffle()`.

`public void shuffle()`

Randomizes the 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 `N == R`, because this doesn't happen often and it does no harm to swap two equal values.

Prints a message that it is shuffling the array, and prints the shuffled array of pieces (piece numbers only).

`public void solve()`

Given a disassembled puzzle (all locations in the two-dimensional array are null, and the one dimensional array holds references to the pieces in random order), assembles it by placing (references to) all the pieces into the two-dimensional array. (Hint: Find the piece that goes in` [0][0]` and put it there; then work across and down, finding each piece as needed.). As each piece is added, prints out a long description of the piece added, the partially completed puzzle, and the list of remaining pieces (just their `id`s).

If a piece cannot be found, prints an error message describing the piece that cannot be found, and terminates the program.

`private int findPiece(long topWanted, long leftWanted)`

Searches the one-dimensional array of pieces for a piece whose `top` edge is `topWanted` and whose `left` edge is `leftWanted`. You will need to use this method when you write `solve()`.

`public boolean isCorrectlyAssembled()`

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. This method does not print anything.

`public void print()`

Prints the two-dimensional puzzle array. Columns should be neatly lined up (this should be easy if `PuzzlePiece.toString()` returns the same length string each time it is called). `print()` should be able to print a partially assembled puzzle (print `"---"` for missing pieces).

In addition (this is new), after printing the two-dimensional puzzle array, this method prints the list of remaining pieces. So the output may look something like this:
```   1   2   3   4
5   6   7 ---
--- --- --- ---

Pieces remaining: 11 9 8 12 10```

You may, if you like, add variables and methods to this class. In particular, it might be helpful to add a method to print the remaining (unassembled) pieces, since this is needed in more than one place.

Note that, if your program works correctly,` isCorrectlyAssembled()` should always return true. You will need to add some code to this program (with appropriate print statements) to make sure that it works correctly.