tart by downloading, unzipping, and importing this (new and improved!) eclipse project.  As before, there are several packages in the code to implement a general search solver.  The main file for running searches is EightPuzzleDemo.java in the demo package. 

You should refer to, but not change, the file EightPuzzleBoard.java ( Uploaded with assignment materials). It shows how the board is implemented, and it provides several methods that will be useful for you.

Next, you should create a new package in the project that is named with your name, in all lowercase.  For example, my package would be named shannonduvall.

You will need to create three classes in your package, and each should implement the HeuristicFunction interface (found in the search.framework package).  This interface requires one method:  double getHeuristicValue(Object state).  The heuristics we will use are discussed below:
Tiles out of place: Simply counts how many tiles (not the blank) are not in the correct position yet.  For the example below, all the tiles are out of place, so the heuristic should return 8.

Manhattan Distance: The manhattan distance between two points is the sum of the horizontal and vertical distances between the points.  The name is supposed to evoke the image of walking city blocks – you dont walk through the block, you only move in a grid fashion along the streets.

So, the Manhattan Distance heuristic counts the total number of row and columns that would need to be traveled to get all tiles in the correct position.  For example: In the above board, the 7 tile is currently in the top left corner, but in the goal state it would be in the center of the bottom row.  So it needs to move one column to the right and two rows down, so it has a Manhattan Distance of 3.  The 2 tile is only one move to the right from its ideal spot.  If you add the distances from all the tiles in the above example (ignore the blank) the answer should be 18.  (3 for the 7 tile + 1 for the 2 + 2 for the 4 + 2 for the 5 + 3 for the 6 + 2 for the 8 + 2 for the 3 + 3 for the 1 = 18).

Finally, you should implement a Row/Column Heuristic.  In this function, you count how many tiles are in the wrong row + the number in the wrong column.  For the above example, the 2 tile is not in place, but it is in the correct row.  The top row has 2 out of place tiles.  The middle row (which should be 3, 4, 5) has one out-of-place tile, the 6.  The bottom row has 2 out-of-place tiles.  Now we notice that no tile is in its correct column.  Therefore the row/column heuristic for this board should be 5 (for rows) + 8 (for columns) = 13.

You may notice that for all these heuristics, a smaller number is better.  You can rest assured
    that the searches are written with this taken into account.  So the file named
    HillClimbingSearch really does gradient descent.

As you write the heuristics code, stick to good code design principles.  Do NOT write a long if-else statement.  Write code that could easily be changed to work for a 4×4 or 5×5 slider puzzle.  Then thoroughly test your code to make sure it works for any possible board.

To remind you, the code will print several statistics for a given search:
The solution (move sequence that solve the puzzle, or a message that no solution was found)
Path cost (the number of moves in the solution sequence)
Nodes expanded (how many states it had to visit to find the goal state.)  This metric relates directly to the amount of time used to get a solution.
Max Queue Size (the largest number of states it had to store at any given point.)  This metric relates directly to the amount of memory used to get a solution.