|
|
|
|
|
CSE143 Autumn 2004 Project #3 Part B
The 15-puzzle game
Due: Monday, December 6 at 9:00 pm. No late assignments will
be accepted.
For this part of the assignment, you will find a way to automatically
solve a 15-puzzle game.
As always, work with your partner.
Grading: You and your partner will receive the same scores on
the programming parts of the project. Programming projects will be evaluated
both for how well the code works and how well it is written and tested,
each on a scale of 0 to 4. Be sure to include appropriate JavaDoc and
other comments in your code, use meaningful names, indent sensibly, 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 and Algorithm
The goal is to automatically find and display a solution for the 15-puzzle
in this assignment. The solution will be displayed by showing each legal
tile
swap, one by one, until the puzzle is solved as described in the
last assignment.
The basic algorithm is called a "Depth-First search". The idea is that,
given the current state of the board, there are at most four states you
could immediately move to (one state for each of the tiles that could
swap with the blank). Once you've moved to one of those states, there
are four states you could move to from there. Once you've moved to one
of those
. . . and so on. At each new state, the question is still, "can
the puzzle be solved from this state"? A depth-first search just travels
from state to state, taking the first legal move it can at each state,
hoping
to
find a solution. If it reaches one, it can return reporting success,
and the algorithm (i.e., the previous trial moves) as a whole returns
a successful solution.
If you're in a maze, you might look for a path out by always taking
the available left turn first, and, when you hit a dead end, going back
and
trying
a right turn at the last place you went left. But what happens if you
reach a point in the maze where you end up in a loop, taking the same
left turns over and over again? You need a way to keep track of where
you've been before. In the case of the 15-puzzle, instead of physical
location in a maze, the "places" you've been are states of the game.
An illustration of this is shown here:
Note that the tree of states shown above is never really built as an
explicit data structure. It's purely conceptual and is meant to help
you understand how to implement the search algorithm. We recommend drawing
it out on
paper, but if you find yourself implementing a tree structure in Java,
you need
to reconsider what you're doing.
To avoid getting into an endless loop, we need to keep track of all
of the game states that have been visited so far. One reasonable way
to do this is to represent each game state as a String that contains
the numbers of the squares in the order that they appear on the board,
separated by blanks or commas. (You need some sort of separator so you
don't have ambiguous numbers like "111", which could mean 11 followed
by 1 or 1 followed by 11. "11,1" or "11 1" removes the ambiguity.) Once
you have decided on a way to represent game states or configurations,
you can use a HashSet to store the configurations that you've already
explored. If a proposed move would reach a state that you've already
seen, then there is no point in exploring that move further.
You know there's a solution from the state you're in if
- Your current state is a solution state
- One of the states you could move to has a solution from it
How do you know if one of the states you could move to has a solution?
Call the search method recursively!
If none of the states you could move to leads to a solution,
then there is no possible solution from the current state and you should
return reporting
failure from that state.
In that case, the search should continue by trying a different move from the
previous state, if there is one. If you call the search method recursively
and it reports success, then you've
found
a
sequence
of moves
that solves
the
puzzle.
Implementation Requirements
- All the requirements from part A, though you can get rid of the
beep or text or other indication of an illegal move if you no longer
allow the user to enter arbitrary moves.
- Solve an arbitrary instance of the 15-puzzle. This instance can
either be one generated when the user hits the "new game" button, or
if the user starts a game and makes a few moves.
- If it's not solvable, tell the user so in some way.
- If it is solvable, show an animation of the process of solving
it, and indicate how many moves it takes. Remember to make the animation
visible to the user (i.e. your program should wait a little bit between
each tile animation).
- Continue 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 moves have led to
a solution.
Suggestions
Though not required, we suggest that you create a method which produces
a random, but solvable puzzle. If you just place tiles randomly,
in some circumstances the puzzle will not be solvable. Instead, it is
possible
to start from a solution state and make random legal moves to scramble
the board, then test your algorithm to see if it finds the solution.
In this way, you know that the board is solvable and that your algorithm
should be able to solve it. More to the point,
you can
set
the number of random moves that set up the
initial state very low,
and know
that the
board is solvable in that many moves. In combination with the bounded
recursion described later, this can make testing much faster. However,
you should test that your program works with random initial configurations,
and that it doesn't choke on unsolvable games.
To show the solution in action, come up with a way to record the steps
on the winning path. That is, once you've found a solution, record the
move you just took to get there on a list of moves to get to a solution.
This can be done either by updating an instance variable, or by returning
a list of moves on the solution path.
Stack overflow error
Java stores information about what methods you've called, and which
methods are still waiting to return, in a structure called the stack.
Each call produces a stack frame. In recursive computing, every time
a method
calls itself, the frame for the first call is still sitting there on
the stack waiting to return. If there are too many recursive calls without
reaching a solution, too many stack frames build up, and the stack overflows,
producing
an exception.
In the
case of the 15-puzzle, there can be very many moves from the start to
the finish, and it's possible in normal operation to overflow the stack.
To
prevent this, we suggest that you add a parameter to the recursive method
to limit the number of recursive calls in the search (i.e., give up and
report failure after some number of recursive attempts to find a solution,
then back up and try other possibilities). Adding a limit like this
is called bounding the recursion.
Extra credit ideas
- There are ways to improve the algorithm to increase the likelihood
of finding a solution quickly. One possibility is to compute a "score"
for each board configuration that is a guess of how far it is from a
solution. This could be some function of how far the different tiles
need to be moved to get in their final location (number of rows + number
of columns). Experiment with different scoring functions and strategies
for picking the next move to try based on those scores to see if you
can find a solution more quickly.
- The requirements specify that you need to show an animation of the
puzzle being solved if your search is able to find a solution. You might
want to add an optional (fast) animation showing the algorithm's attempts
to find a solution.
- You might also add some pause/resume/step controls to your user interface
to run the search or the final animation a step at a time to help you
visualize or debug the search.
- Display a picture instead of numbers so that when the tiles are in
order a nice picture will be displayed.
- Allow the user to select an image to be used.
- Anything else interesting your can come up with.
What to Turn In
Use this online turnin form to
turn in the files that make up your program and tests.
|
UW Home 
