Objectives

• Implement Puzzle-8 using a picture the user takes with the phone camera.

Aim

The preparation for this workshop should have lain the groundwork for Puzzle-8 so you should be able to proceed with the more complicated parts of the game.

The three classes that implement the game functionality are:

• PuzzleBoardView inherits from View and is responsible for drawing of a puzzle board in the UI. It also handles the shuffling (and later the solving) of the puzzle
• PuzzleBoard represents the current state of the puzzle board
• PuzzleTile is responsible for drawing and manipulating a single tile

The PuzzleTile implementation is provided so take a moment to read through it.

You can now delete the ImageView that you used to test the picture-taking functionality. Instead, we will display the photo in a PuzzleBoardView. But because PuzzleBoardView is a custom-type, it is added to the UI programmatically rather than using the UI editor. The code to do this is provided in the PuzzleActivity.onCreate method.

Next, implement the constructor for PuzzleBoard. It should take the passed-in Bitmap object and divide it into NUM_TILES x NUM_TILES equal-sized pieces.

Hint

You can use the Bitmap.createBitmap and Bitmap.createScaledBitmap methods to do so.) Then use each "chunk" of the bitmap to initialize a tile object. Remember to leave the last tile null to represent the 'empty' tile!

You should then display these tiles on the board (removing the ImageView you may have used to test the picture-taking functionality).

Try running your app and make sure that the photo you take is chopped up into appropriately-sized tiles and that the unshuffled puzzle is properly rendered on the screen. Because the tap functionality is provided, you should also be able to manually shuffle the board.

Next, we will implement the shuffle functionality. One option would be to implement shuffling by randomly swapping tiles, but that could lead to a puzzle that cannot be solved. In order to avoid this, we will instead make a number of random moves starting with the solved puzzle to create the shuffled puzzle. Implement PuzzleBoard.neighbours which is a method that returns an ArrayList of all the PuzzleBoard configurations that are possible by moving one tile in the current PuzzleBoard. Note that depending on where the empty square is, there could be 2, 3 or 4 possible moves. So implement the neighbours method to:

• locate the empty square in the current board
• consider all the neighbours of the empty square (using the NEIGHBOUR_COORDS array)
• if the neighbouring square is valid (within the boundaries of the puzzle), make a copy of the current board (using the provided copy constructor), move the tile in that square to the empty square and add this copy of the board to the list of neighbours to be returned

The implementation of PuzzleBoardView.shuffle is then a matter of repeatedly updating PuzzleBoardView.puzzleBoard to a randomly selected value from PuzzleBoardView.puzzleBoard.neighbours(). Don't forget to call invalidate() at the end of the shuffle method in order to update the UI.

You can now test your app by taking a picture, shuffling it and manually trying to solve the puzzle. If you enjoy a challenge, try updating NUM_TILES to 4 and manually solving the puzzle. Note that you can also vary the difficulty of the puzzle with the content of the picture that you take.

Timing

In total, this workshop activity should take you around 3-4 hours to complete.

Milestone 1: 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.

Info

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.
• A 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

Info

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

Milestone 2: 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.

Extensions

These extensions offer a variety of different ways you might extend the basic Puzzle-8 functionality:

• Replace the use of the standard Java PriorityQueue object, with your own min-heap-based implementation of a priority queue. You only need to support a simple constructor and three methods (add, remove and isEmpty) and you can make your implementation PuzzleBoard-specific (it does not need to handle generic types).
• Animate the movement of each tile (rather than having them jump into position)
• Support playing the game by swiping the tiles instead of tapping them
• Add a "settings" activity that allow the user to select the desired number of tiles
• Instead of using the thumbnail provided by the ACTION_IMAGE_CAPTURE intent, try using the full-definition image taken by the camera.
• Allow the user to select taking a new photo or using a photo from their image folder

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.