CIT 590 Jigsaw Puzzle
Spring 2009, David Matuszek

Purposes of this assignment

To give you more experience with arrays, classes, and methods.
To give you an easier assignment than the last one.

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:

	0
0		143
	171

	0
143		777
	191

	0
777		298
	451

	0
298		0
	380

	171
0		212
	188

	191
212		317
	167

	451
317		304
	155

	380
304		0
	441

	188
0		667
	0

	167
667		850
	0

	155
850		240
	0

	441
240		0
	0

All outside edges will be zero.

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

You should have these classes:

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. When you construct a puzzle piece, you must supply values for all four sides.
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 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; since we will probably only use the toString() method to get something to print, we can "reduce" them to three digits with (number & 0x3FF) % 900 + 100. This may give use some duplicate numbers (and it will turn the "zero" edge numbers into 100) but since we will use the original long numbers in fitting pieces together, this won't hurt anything.

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)

Uses the PuzzleCreator to create a puzzle, prints it, then uses the PuzzleSolver to solve the puzzle, uses the SolutionChecker to test whether the puzzle was solved correctly, and prints the assembled puzzle.

public void print()

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

+-----------+-----------+-----------+-----------+
|    100    |    100    |    100    |    100    |
|100     143|143     777|777     298|298     100|
|    171    |    191    |    451    |    380    |
+-----------+-----------+-----------+-----------+
|    171    |    191    |    451    |    380    |
|100     212|212     317|317     304|304     100|
|    188    |    167    |    155    |    441    |
+-----------+-----------+-----------+-----------+
|    188    |    167    |    155    |    441    |
|100     667|667     850|850     240|240     100|
|    100    |    100    |    100    |    100    |
+-----------+-----------+-----------+-----------+

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 it's nextLong() method with no parameters.

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

This method creates and returns a puzzle as a one-dimensional array of PuzzlePieces. So that the puzzle isn't trivial to solve, the array is shuffled before it is returned.

(Implementation note: To create the puzzle, you probably want to create and put puzzle pieces into a two-dimensional array, and then copy the pieces into a one-dimensional array to return to the user.)

public 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.).

If a piece cannot be found, the method should print an error message describing as much as it can about the piece that cannot be found, and terminate the program (call System.exit(1);).

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. This method can be used by the solve method.

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

You will be assigned a partner for this assignment. One of you should write the JigsawPuzzle and PuzzleSolver classes, while the other should write the PuzzleCreator and SolutionChecker classes. (The PuzzlePiece class is trivial, and you should have already written that by the time lab is over.)

To test your program before you get the part that your partner is supposed to write, you will need to create some "fake data." I suggest that each of you write an additional Test class, with a public static void main(String[] args) method, to use in testing your part of the program. You need not hand in this test class with the rest.

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
Name to use for Blackboard: JigsawPuzzle_yourName_partnersName

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.

Due Date

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