15-121 Fall 2009

Homework Assignment 7

Slide Puzzle


Overview:

Sliding tile puzzles (follow this link for an interactive puzzle) are common children's games and party favors. The slide puzzle consists of a three by three board with eight numbered tiles and a blank space, denoted by a zero. A tile adjacent to the blank space can slide into the space. The objective is to figure out the steps needed to get from one configuration (which is is an arbitrary arrangement of the tiles), for example,

1 2 3
4 0 5
7 8 6

to the goal configuration:

1 2 3
4 5 6
7 8 0

Finding such a solution of the general n2 - 1 puzzle is known to be NP-complete, and furthermore, the best known algorithm for solving the eight puzzle optimally is A*.


Objectives:


Assignment:

In this assignment you will implement a program that uses BFS search and A* search to solve the Eight Puzzle game. Your program will take an initial board position, and then try to find a sequence of moves from the initial position to the goal position. Moves are represented by moving the blank space left, right, up, or down. For example, suppose we wanted to solve the puzzle shown above. This could be accomplished by the following sequence of moves (we represent a move as the direction the empty space moved):

 1 2 3     1 2 3     1 2 3
 4 0 5  R  4 5 0  D  4 5 6
 7 8 6     7 8 6     7 8 0
 initial             goal

where R=right, L=left, U=up, D=down. So we can solve this puzzle with the sequence of moves "RD".


Game Tree:

Given the initial board:

1 2 3
4 0 6
7 5 8

we can determine all the boards that are one move away

The next boards

Repeating this recursively will create a game tree of boards with the initial puzzle at the root

A tree representation of the problem space

This is not a binary tree. Some nodes have two children, some have three, and some have four. Also note that the tree has no leaf nodes, since every board can be transformed into another board by moving a tile. As a consequence of this, there is an infinite number of nodes in our tree.

We label the edges connecting the nodes in the tree according to the empty space move. That it is, instead of thinking of moving a specific tile in a specific direction, we can think of moving the empty space in the opposite direction.

With this representation, we are interested in the finding the shortest path from the root node to the solution node.

Here are some questions to consider about the puzzle:

Does every board have a solution? No. All solvable puzzles must be rearrangements (via moving the empty space around) of the solved puzzle. It is possible to make a board that does not fit this description (for example, consider physically breaking a tile out of the puzzle and putting it somewhere else). We will only concern ourselves with solvable puzzles.
Does every board have a unique solution? No. Consider a solution to a puzzle. Now add a cycle to that solution (such as "move the empty space to the right and then back to the left") and we have another solution.
Does every board have a unique OPTIMAL solution? Not necessarily. There could be several shortest paths to a goal board. Your program should return just one of them.

Game board:

A board is represented by an instance of the TileBoard class using a string of the puzzle tiles (0 is the empty space). For example, the puzzle:

1 4 6
0 2 3
6 8 7

is stored as "146023687". The class also stores the sequence of moves (a string "LURD..." etc)generated from the start board to this board.

You will need to design and implement a functionality for manipulating boards. Try to be efficient in both memory and time. Make sure to comment your design decisions!


BFS

You implement a BFS over the game tree using a queue (use java.util.LinkedList as a Queue) of TileBoards. You will notice that BFS requires considerable computer memory resources, due to the size of the game tree. We suggest the following two ideas dealing with memory issue:


A* Algorithm

The A stands for "algorithm", and the * indicates its optimality property.

The problem with a breadth-first search is that eats too much resources and takes too long. One way to make it faster is to prioritize boards according to there distances to the goal board. This will avoid considering boards that are relatively far away from the goal board. Such class of search algorithms is called heuristic-based searches.

We shall define a heuristic function H(S) that estimates the distance (i.e., the length of the path) from a current board S (also called a state) to the solution board:

H(S) = A(S) + E(S)

where A(S) is the actual distance from the inital state to this board, and E(S) is the estimated distance from S to the goal state. We will compute A(S) from the game tree we constructed so far, and we will define E(S) as the "Manhattan Distance" between S and the goal state.

A*-search uses H(S) as the way of determining which board to consider next. A*-search works correctly as long as H(S) is an underestimate of the distance between the current state and the goal state (try to prove this by yourself).

For our implementation, use a java.util.PriorityQueue of TileBoards that is ordered by H(S). You will need to write a comparator to get this work.


Manhattan distance:

The Manhattan distance heuristic is used for its simplicity and also because it is actually a pretty good underestimate (aka a lower bound) on the number of moves required to bring a given board to the solution board. We simply compute the sum of the distances of each tile from where it belongs, completely ignoring all the other tiles. For example, the Manhattan distance between "213540678" and "123456780" is 9:

2 1 3     1 2 3           1 2 3 4 5 6 7 8
5 4 0     4 5 6           ---------------
6 7 8     7 8 0           1+1+0+1+1+3+1+1 = 9

This is so, because the tile "1" is 1 move away, the tile "2" is 1 move away, the tile "3" is 0 moves away, the tile "4" is 1 move away, the tile "5" is 1 move away, the "6" tile is 3 moves away, the "7" is 1 move away, and the "8" is 1 move away.

Note that we do not consider the empty space, as this would cause the Manhattan distance heuristic to not be an underestimate.

Another example:

6 4 7     1 2 3           1 2 3 4 5 6 7 8
8 5 0     4 5 6           ---------------
3 2 1     7 8 0           4+2+4+2+0+3+4+2 = 21

Additional Requirements:

Requirement 1:

When you solve a board (either in solvePuzzleBFS or solvePuzzleAStar) return both the required moves AND the number of boards considered by your algorithm (i.e. the size of the problem space considered). We have written SolverSolution class that you can use for this purpose. You should find that the A* Search considers far fewer boards that the BFS search, and is thus much faster.

You are to present a text file in which you compare the number of nodes that each search algorithm examines on 3 (three) initial boards of your choice. In order to demonstrate that A* is superior to standard BFS, create and fill in the following table:

   Initial Board      BFS search    A* search  
     
     
     

Requirement 2:

If you've been paying attention to how we build a game tree, you might have noticed that the gane tree contains multiple instances of the same board. You are required to develop a way of preventing duplicate boards. You will see that the performance of your implementation increases since the number of boards considered decreases. With this technique you should be able to search (using BFS) the whole game tree to the depth of the solution board.

You need to demonstrate this new technique by filling in the table in which you compare the number of nodes that each search algorithm examines

   Initial Board      optimized BFS search    optimized A* search  
     
     
     

Put these tables in a text file and turn them in with your submission.


Testing:

Test your solution on the following starting boards. Recall that the optimal solution is not necessarily unique (so make sure yours works) but there is always an optimal number of moves.

  board  | number of moves | solution(s)
123405786	2		RD
123745086	4		URRD
123480765	5		DLURD
413726580	8		LLUURDDR
162530478	9		LURDLLDRR
512630478	11		LLURRDLLDRR
126350478	13		ULDLDRRULURDD
356148072	16		RRUULLDRDRUULDRD
436871052	18		URRULDDRULDLUURDRD
302651478	21		DRULDLURRDLLDRRULURDD or DLURDRULDLURDRULDLDRR
012345678	22		RDLDRRULLDRUURDDLLURRD or DRRULLDDRUURDLLURRDLDR
503284671	23		LDDRRULLDRRULLDRUULDDRR
874320651	25		DLULURDRULDDLUURDRDLLURRD
876543021	28		UURDRDLLUURDRULDDRULDLUURDRD or UURDLDRURDLLUURDRULDDLUURDDR
876543210	30		ULLURDDRUULDDLUURDDRUULDDLURRD or ULULDDRUULDDRUURDDLUURDLULDRDR

We recommend that you test your solution rigorously. Try using it to solve puzzles that you create yourself or find on the internet (such as the link provided above).


Starter Code:

Download the following files Do not change any of the starter code!

What to submit:

You need to FTP the following java files

  1. SlidingSolver.java
  2. TileBoard.java

Also turn in the text file you created for Requirement 1 and Requirement 2.

Do not submit anything else like zip files, folders, desktops, class files. Failure to do so will result in a 10 point penalty.


Grading

Your assignment will be graded first by compiling and testing it. After that, we will read your code to determine whether appropriate classes were used, as well as judge the overall style and modularity of your code. Points will be deducted for poor design decisions and un- commented, or un-readable code as determined by your TA.

Here is the point breakdown:


Victor S.Adamchik, CMU, 2009