Homework Assignment 7

Slide Puzzle

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 n^{2} - 1 puzzle is known to be NP-complete, and furthermore,
the best known algorithm for solving the eight puzzle optimally is A*.

- Representing a seemingly complex problem in a workable form
- Construct and analyze game trees
- Understand and implement heuristic search
- Practice working in small teams to solve problems, design algorithms and write code

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".

Given the initial board:

1 | 2 | 3 |

4 | 0 | 6 |

7 | 5 | 8 |

we can determine all the boards that are one move away

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

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.

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!

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:

- stop BFS when you reach boards with 20 moves away from the initial board, and return
`SlidingSolution.NO_SOLUTION`

- increase the memory heap size. Here is an example:
java -Xmx500m SlidingSolverDriver

where -Xmx specifies the max heap size. Heap memory is an internal memory pool that dynamically allocated by your application as it's needed. The max heap size for Windows runs from 1.3G to 1.6G depending upon the machine.

In Eclipse, you can do this by going Run → Run Configurations → Arguments → VM Arguments.

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.

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

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 |

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.

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).

You need to FTP the following java files

- SlidingSolver.java
- 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.

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:

- Style and design of your TileBoard representation - 15 points
- Correctness of your Breadth-first search solution algorithm - 15 points
- Correctness of your A-Star search solution algorithm - 30 points
- Correct implementation of the "Manhattan Distance" heuristic - 15 points
- Requirement 1 - 5 points.
- Requirement 2 - 10 points.
- General coding style - 10 points.

Victor S.Adamchik, CMU, 2009