8 puzzle heuristics

I discussed several heuristics in class as well as how many heuristics can be derived from a formal description of the problem. This is discussed in a little detail in your text in Section 4.2.

Here are some heuristics, some of which I covered in class:

Nilsson's Sequence Score: h(n) = P(n) + 3 S(n)
P(n) is the manhattan distance of each tile from its proper position.
"The quantity S(n) is a sequence score obtained by checking around the noncentral squares in turn, allotting 2 for every tile not followed by its proper successor and 0 for every other tile, except that a piece in the center scores 1."
This might be easier to understand if you know that the goal state that Nilsson uses is represented by: (1 2 3 8 space 4 7 6 5). This heuristic is not admissible.
X-Y: decompose the problem into two one dimensional problems where the "space" can swap with any tile in an adjacent row/column. Add the number of steps from the two subproblems.
Number of tiles out of row plus number of tiles out of column.
n-MaxSwap: assume you can swap any tile with the "space". Use the number of steps it takes to solve this problem as the heuristic value.
n-Swap: represent the "space" as a tile and assume you can swap any two tiles. Use the number of steps it takes to solve this problem as the heuristic value.

Note that some of these heuristics involve performing a search to find the value of the heuristic. In these cases, you want the additional time spent evaluating the heuristic to be more than offset by the decrease in the effective branching factor.

You could create the "perfect" heuristic by having it perform an A* search to find the exact number of steps to reach the goal, but that would not be a good solution to this problem!