Note: this is a high difficulty exercise.
Start by reviewing the queue and heap data structures. Then bring the two together with some readings on priority queues. This content is not simple so take some time to read it carefully and understand it as you will be expected to implement a heap-based priority queue during the workshop.
Implement: Puzzle-8. This game goes by many names: some call it puzzle-8 or 8-puzzle or 15-puzzle. The idea is to slide tiles around to form an image or to recreate a numerical sequence.
Here is a physical example of this classic game:
If you have not seen this game before, each tile can slide either horizontally or vertically into the empty space in order to reorder the tiles.
For our version of this game, we be using an image of R2D2 to create the tiles.
You can read more about the game on Wikipedia.
Tour of the code
We have provided the UI for this game: all you need to do is code the solver portion.
The starter code for this activity is composed of four classes:
PuzzleActivity which is the lone activity for this program:
onCreate: in addition to the boilerplate, the given implementation programmatically adds the
PuzzleBoardView object to the UI.
onOptionsItemSelected: just boilerplate
solve: trivial handlers for the two buttons
PuzzleBoardView, a custom
View responsible for drawing the puzzle on screen
PuzzleBoardView: Constructor. Given implementation is complete.
initialize: to add a picture to the view.
onDraw: called by the system when the view should be redrawn. Note the code that will animate the solution once you implement the solver.
shuffle: the actual handler for the "Shuffle" button. You will need to implement this.
onTouchEvent: code that handles user clicks
solve: where your solver code will go
PuzzleBoard which represent the state of the puzzle. This class is separate from
PuzzleBoardView because there will always be only one
PuzzleBoardView but we will deal with multiple
PuzzleBoard objects when we implement the shuffle and solve functionality
NEIGHBOUR_COORDS: a constant array storing the relative coords of all the neighbors of one tile. This will make possible to check neighbors with a for-loop rather than 4 if-statements.
PuzzleBoard: Constructor. This should handle breaking up the given image into tile-sized chunks.
PuzzleBoard: Copy constructor. This constructor creates a puzzle board that copies the state of another puzzle board. This will be handy when implementing
reset: Part of the solver functionality
equals: Tests whether two boards are equal by checking whether their tile configuration is the same.
draw: Called by
onDraw. Makes each tile draw itself.
click: Called by
onTouchEvent. Determines which tile was clicked and attempts to move it.
tryMoving: helper for
resolved: Checks whether the current board is solved. This is the reason why we store indexes in each tile.
XYtoIndex: helper method to convert between two-dimensional coordinates and positions in the ArrayList.
swapTiles: private helper. Does what it says.
neighbours: will create a list of all board configurations that can be reached by moving a single tile in the current board.
priority: computes the priority of the current board. This will be explained as part of the instructions for the solver.
PuzzleTile which represents a single tile. This is fully implemented for you.
PuzzleTile: Simple constructor that stores the given index and bitmap.
getNumber: Getter for the tile index.
draw: Draws the bitmap on the given canvas at the given location.
isClicked: Determines whether the touch location falls within the tile.
It is fun to play puzzle-8 for a while but wouldn't it be nice to let the computer solve it for you when you get stuck? You will implement a solver that uses a best-first search algorithm to find the quickest solution to the current puzzle. You will do so by implementing the A* search algorithm, an algorithm from AI that is widely used in pathfinding and graph traversal.
We have already defined
PuzzleBoard to represent a state of the board (e.g. the current state or the states generated by moving a single tile). You will add to this class two members:
- An integer called
steps representing the number of steps required to reach the given state. You should update
PuzzleBoard's copy constructor to set steps to one more than the value passed in with
PuzzleBoard object called
previousBoard referring to the previous state of the board before reaching the current state. You should set
otherBoard in the copy constructor.
Our search algorithm then consists of maintaining a
PriorityQueue (part of the Java library) of possible board states and considering the best state we have so far and adding all of its neighbours onto the
PriorityQueue until we solve the puzzle. The success of this approach relies on the use of an appropriate priority function associated with each
PuzzleBoard. We will use a Manhattan priority function which is the sum of the distances (sum of the vertical and horizontal distance) from the blocks to their goal positions, plus the number of moves made so far to get to the state.
For example with a starting configuration of:
8 1 3
7 6 5
And a desired target of:
1 2 3
4 5 6
We have the following Manhattan distances for each of the blocks, which is simply the number of steps from the blocks current position to its correct position.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
1 | 2 | 0 | 0 | 2 | 2 | 0 | 3
This results in a Manhattan priority of 10 (sum of the second row) + number of moves so far
Using this strategy works because to solve the puzzle from a given
PuzzleBoard, the total number of moves we need to make (including those already made) is at least its priority.
Consequently, as soon as we dequeue a state, we have not only discovered a sequence of moves from the initial board to the board associated with the state, but one that makes the fewest number of moves.
So start by implementing the
PuzzleBoard.priority method to return the Manhattan distance + steps. Then implement
- Instantiate a
PriorityQueue object (this will require you to createa custom
PuzzleBoardComparator that compares the priority of two boards. Android Studio is helpful in creating the template for you)
- Add the current
PuzzleBoard to the queue (0 moves, and a null previous state)
Then while the queue is not empty:
- Remove from the priority queue the
PuzzleBoard with the lowest priority
- If the removed
PuzzleBoard is not the solution, insert onto the
PriorityQueue all neighbouring states (reusing the neighbours method).
- If it is the solution, create an
ArrayList of all the
PuzzleBoards leading to this solution (you will need to create a getter for
PuzzleBoard.previousBoard). Then use
Collections.reverse to turn it into an in-order sequence of all the steps to solving the puzzle. If you copy that
PuzzleBoardView.animation, the given implementation of
onDraw will animate the sequence of steps to solve the puzzle
A critical optimization
After implementing best-first search, you will notice one undesirable feature: states corresponding to the same board position are enqueued on the priority queue many times. To prevent unnecessary exploration of useless states, when considering the neighbours of a state, don't enqueue the neighbour if its board position is the same as the previous state.