CIT 591 Assignment 10: Jigsaw Puzzle
Fall 2011, David Matuszek

Purposes of this assignment

• To get you started using multiple classes.
• To give you more experience with unit testing.

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:

All outside edges will be zero.

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

Unit test these methods: lastThreeDigits and toString (in PuzzlePiece), shuffle (in PuzzleCreator), findPiece (in PuzzleSolver), and isCorrectlyAssembled (in SolutionChecker).

You should have the following classes. Each class should begin with a Javadoc comment telling the purpose of the class, and should have an @author tag. The main class (JigsawPuzzle) should have @author tags for both you and your partner.

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. For each of the four sides, it will do the following: If any parameter is exactly -1, it will choose a random long number for that side. If the parameter is any other number, it will use the parameter value for that side. (We can do this because, although it is possible for the random number generator to return -1, that will only happen about once every ten billion billion tries.)

Note: In order to avoid passing in -1 as a "magic number" (a number whose meaning is not obvious from context), give it a name in your class; define the varible final long RANDOM = -1;

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 make the variables private so that other classes cannot change those values. (You don't want people jamming in pieces where they don't really fit. ).

public static int lastThreeDigits(longNumber)

Returns, as an integer, the last three digits of the provided long number. Since the number could be negative, begin by taking its absolute value, then modding the result with 1000.

 

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, so abbreviate" them with the lastThreeDigits method. This may give use some duplicate numbers, but we will only use this method when we want to print out pieces; we will use the original long numbers in fitting pieces togethe.

public class JigsawPuzzle

This is the "main" class--that is, it holds the main method.

public static void main(String[] args)

Call the program with command-line arguments: args[0] as the number of rows, and args[1] as the number of columns. (In Eclipse: Run → Run Configurations... → Arguments → Program arguments:.) Print an error message and quit if you don't get exactly two command line arguments, or if they do not represent positive integers within a reasonable range.

Use the PuzzleCreator to create a puzzle. Save the puzzle as an instance variable, print it (as a list of puzzle pieces), then use the PuzzleSolver to solve the puzzle, use the SolutionChecker to ensure that the puzzle was solved correctly, and print the assembled puzzle.

public void print(PuzzlePiece[][] puzzle)

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

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

You can use System.out.printf with the %03d format to print numbers in the range 0 to 999, as shown above.

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

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

This method creates the puzzle as a two-dimensional array, but then shuffles and returns it as a one-dimensional array. (If you didn't shuffle the pieces, it wouldn't be much of a puzzle, would it?)

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

PuzzlePiece findPiece(long topWanted, long leftWanted, PuzzlePiece[] pieces)

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.

If a piece cannot be found, the method should create and throw a RuntimeException(message). The message should include information about the piece being searched for. Of course, if the PuzzleCreator did its job properly, this should never happen.

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

If you are unable to work closely with your partner, one of you should write the JigsawPuzzle and PuzzleSolver classes, while the other should write the PuzzleCreator and SolutionChecker classes. In this case you may need to create some "fake data" for testing purposes.

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

Due Date

Before 6am, December 2. Zip your entire project and submit via Sakai. As this is a pair programming assignment, only one of you should submit the assignment, with both your names prominently displayed, as described above. As always, only assignments submitted via Sakai will be accepted--do not send your program by email. A late penalty of 5 points per day (out of 100 points) will apply.