Related Problems: N-Puzzle Type:heuristic function

h(n) = P(n) + 3S(n)

P(n) is the Manhattan Distance of each tile from its proper position.
S(n) is the sequence score obtained by checking around the non-central squares in turn, allotting 2 for every tile not followed by its proper successor and 1 in case that the center is not empty.


This heuristic is not admissible, and assume that the goal state is represented by (1 2 3 8 space 4 7 6 5).