UW Home     CSE Home   Announcements    Message Board    Contact Info 

 
 
 

CSE143 Autumn 2004 Project #3 Part A

The 15-puzzle game

Due: Wednesday, November 24, at 9:00 pm. No late assignments will be accepted.

In this assignment you will be creating a 4 X 4 grid that represents a 15- puzzle game. This game has 15 orderable objects (tiles) and one empty slot to allow objects to move. It usually looks something like this:

1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

For part A you will generate random initial orderings of the tiles, then allow the user to manipulate the tiles in the square in order to come up with a solution. In part B you will actually automate the solution finding process.

Work with your assigned partner. The same rules as always apply: try to do most of the actual coding while sitting at the same computer, trading off the keyboard. The two of you should turn in a single set of files. After the final part of the project is done, each of you will individually write a final report.

Grading: When the project is complete, your project will be evaluated both for how well the code works and how well it is written and tested. For this part of the project, we will try to give you quick feedback on the scale of 0-3: 3 = no major problems, 2 = something needs to be fixed, 1 = serious trouble, and 0 = no credible effort. For all phases of the project, be sure to include appropriate JavaDoc and other comments in your code, use meaningful names, indent sensibly, provide toString() methods where appropriate, and so forth.

Keep track of the major design decisions, algorithms, and tests you perform to verify your code is working. You will be asked to include a summary of these in the report that you will write individually at the end of the final part of this project.

Overview

The 15-puzzle is originally displayed with a random ordering of numbers 1 through 15 plus a blank (empty) square. The user then needs to move one square at a time until the numbers are ordered (or until the user gives up since these games don't always have a solution). A square can only be moved if there is an adjacent free slot to move to. A puzzle is said to be solved if the numbers are in increasing order and the empty slot is either in the top left corner (next to 1) or in the bottom right corner (next to 15)

What we're doing for part A

You will display a 4 X 4 grid of numbers 1 through 15 in random order.You can look at the Random class java documentation to get ideas about how to implement this. The user will then have to swap the empty slot with a numbered slot one at a time using the mouse and, optionally, the keyboard. Furthermore, an encouraging message should be displayed if the user solves the game. This message should include the number of moves it took for the user to complete the game.

Implementation Requirements

The purpose of this part of the project is to get you more used to collections and their implementation and to practice graphical event driven interfaces one more time. Here are the requirements for your program:

  • You should keep the internal representation of the 15-puzzle using a Collection that we've discussed in class.suitable data structure like a Collection or an Array. You could use an ArrayList and map each cell to a corresponding row and column in the puzzle. You could also implement this using a bi-dimensional array. You can choose any data structure as long as you use a Collection to represent the puzzle
  • You should think about a sensible way in which to represent the empty slot. One way to do it would be to have a 0th or a 16th cell in your data structure that you graphically represent as an empty slot
  • You should give the user a way to manipulate the puzzle to make legal swaps between the empty slot and its neighbors. One way to do this is by representing each slot using a button. When the user clicks on a numbered button, if the empty slot is next to it it swaps them. Another way is by creating a graphic representation that reacts to key strokes and/or mouse clicks. If you implement this using mouse clicks you need to think about a way to translate mouse coordinates to the slot represented in the GUI
  • If the user trys to make an illegal move, your game should provide some feedback by either beeping, flashing, or displaying an appropriate message.
  • You should keep track of how many legal moves has the user made and display a message when the puzzle has been completed.
  • You should implement a "new game" button in the GUI. When "new game" is clicked, the program should generate a new random permutation of the numbers 0-15 and an empty slot.
  • Remember to use the MVC model to separate the details of the user interface from the game engine, which decides if a move is legal, updates the state of the game, and checks for whether the user has won.
  • You should include some basic JUnit tests to verify that the model correctly processes moves.

Extra credit ideas

As usual, we invite you to use your imagination to extend the project in ways you find interesting. Here are a couple of ideas to get you started.

  • Display a picture instead of numbers so that when the slots are in order a nice picture will be displayed
  • Create "rewind" or "start over" buttons that undo the previous move or start over with the same initial configuration (instead of a new random configuration).

There's a lot of room in this project to be creative so have fun with it!

What to Turn In

Use this turnin form to turn in the files that make up your program and tests.