Due by 11:59pm Wednesday, April 24
Finish the heuristic-search version of the 8-puzzle solver from Lab 12. Complete the table from part 7 of the lab worksheet showing the performance of your program on each of the starting states under the various conditions given in the table. You should test your heuristic functions individually, to make sure they work as expected. To help you out, the correct heuristic values for each of the starting boards are shown below. For example, calling z.heuristic2(goal2) should return 15.
| Board/Goal | heuristic1 | heuristic2 |
|---|---|---|
| a / goal1 | 2 | 2 |
| b / goal1 | 5 | 6 |
| c / goal1 | 7 | 8 |
| d / goal1 | 7 | 8 |
| e / goal1 | 7 | 8 |
| f / goal1 | 7 | 12 |
| g / goal1 | 8 | 13 |
| h / goal1 | 8 | 16 |
| x / goal2 | 8 | 19 |
| y / goal2 | 7 | 11 |
| z / goal2 | 8 | 15 |
To implement your Manhattan distance heuristic function (heuristic2), it may be helpful to add the following two methods to your Board class, which take a tile numbered from 1 to 8 as input, and return the tile's 0-based row or column number on the Board. For example, if tile #8 is currently located in the lower left corner of the Board, it will be stored in the tiles array at index position 6, so calling find(8) will return 6. This corresponds to row 2, column 0 on the Board, so calling row(8) will return 2 and calling column(8) will return 0.
// returns the row number of the given tile
public int row(int tile) {
return find(tile) / 3;
}
// returns the column number of the given tile
public int column(int tile) {
return find(tile) % 3;
}
To test your heuristic functions on the sample boards provided in the Board class, you can add the code below to the main method of your Board class and then click Run in DrJava. The output should match the values given in the table above.
public static void main(String[] args) {
String[] names = { "a/goal1", "b/goal1", "c/goal1", "d/goal1", "e/goal1", "f/goal1",
"g/goal1", "h/goal1", "x/goal2", "y/goal2", "z/goal2" };
Board[] boards = { a, b, c, d, e, f, g, h, x, y, z };
Board[] goals = { goal1, goal1, goal1, goal1, goal1, goal1, goal1, goal1, goal2, goal2, goal2 };
System.out.println("Board/Goal h1 h2");
for (int i = 0; i < names.length; i++) {
System.out.printf("%8s %4d %4d\n", names[i],
boards[i].heuristic1(goals[i]), boards[i].heuristic2(goals[i]));
}
}
Turn in your lab worksheet during class, with the table from part 7 filled in.
Submit your Board.java and EightPuzzle.java files using the Homework Upload Site. You don't need to submit any other files for this assignment.
If you have questions about anything, just ask!