CIT 590 Jigsaw Puzzle
Spring 2009, David Matuszek
Create and solve a "jigsaw puzzle."
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.
To simplify the problem, you never need to rotate pieces; the "top" side is always up.
You should have these classes:
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()
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()
[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
longnumbers in fitting pieces together, this won't hurt anything.
PuzzlePieceonce it has been created. Do not add such methods to this class.
This is the "main" class--that is, it holds the
public static void main(String args)
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 | +-----------+-----------+-----------+-----------+
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
number generator and use it's
nextLong() method with
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 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
 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
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
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",
Note that, if your program works correctly,
isCorrectlyAssembled() should always return
You will be assigned a partner for this assignment. One of you should
while the other should write the
SolutionChecker classes. (The
PuzzlePiece class is
trivial, and you should have already written that by the time lab is
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
static void main(String args)
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.
Thursday, February 26, before midnight. Turn in one program (to Blackboard) for your group.