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:

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 longs 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 ids).

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.

Grading:

Besides testing whether your program works, we will look for good comments (you can start with the above method descriptions, and modify them as necessary) and correct formatting. Both partners on the project will receive the same grade.

Due date:

Thursday, October 14, before midnight. Turn in one program (to Blackboard) for your group.