Puzzle 8

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.

### 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.
• onCreateOptionsMenuonOptionsItemSelected: just boilerplate
• shuffleImage and 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 neighbors below.
• 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 PuzzleBoardView's onDraw. Makes each tile draw itself.
• click: Called by PuzzleBoardView's onTouchEvent. Determines which tile was clicked and attempts to move it.
• tryMoving: helper for click.
• 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.

### Puzzle-8 solver

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 otherBoard.
• PuzzleBoard object called previousBoard referring to the previous state of the board before reaching the current state. You should set previousBoard to 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
4   2
7 6 5


And a desired target of:

1 2 3
4 5 6
7 8


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 PuzzleBoardView.solve to:

• 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 ArrayList to 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.