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:
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
The most difficult methods are the
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.
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
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:
This class describes a single piece of the puzzle. It holds five
privateinstance variables: An
intthat 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.
There are no methods that change the instance variables of the
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
1to the static variable
id, then use the result as the piece number. (For this to work, it is essential that the
Each time you create a piece, print a message of the form
. Use the piece's
Created piece 3: [0 12 552 -291]
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
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
idof this puzzle piece, as a three-character right-justified
String. That is,
" 25"instead of just
"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
, where (for readibility) the edge numbers have been reduced to three or fewer digits by dividing by
number: [top left right bottom]
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:
. This method prepares a string for printing, but it does not itself print anything.
3: [0 12 552 -291]
PuzzlePieceonce it has been created. Do not add any additional methods to this class.
This class describes the entire puzzle. It contains two arrays: A one-dimensional array of
PuzzlePieceused to hold all the puzzle pieces when the puzzle is not assembled, and a two-dimensional array of
PuzzlePieceto hold the assembled pieces.
public Puzzle(int rows, int columns)
This constructor is fairly complex. It does the following:
- Prints a message that says it is about to create a jigsaw puzzle, and tells the number of rows and columns in the puzzle.
- Creates the necessary one- and two-dimensional arrays. All elements of these arrays will initially be null.
- 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
solvemethod does something quite different, so we can't just call it to do this for us.)
- 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)
Puzzleand calls its
doPuzzle()method. The number of rows and columns in the puzzle should be taken from
public void doPuzzle()
print()to print the (unassembled) puzzle and the array of puzzle pieces.
solve(0)to assemble the puzzle.
- 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
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:("Down to" means step byfor N from the array length down to 1: choose a random number R, where 0 <= R < N swap array locations N and R
-1.) Note that it is not worth checking whether
, because this doesn't happen often and it does no harm to swap two equal values.
N == R
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
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
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
leftWanted. You will need to use this method when you write
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
trueif all pieces "fit together",
falseotherwise. 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.
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.
Thursday, October 14, before midnight. Turn in one program (to Blackboard) for your group.