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

Related Problems:N-PuzzleType:heuristic functionh(n) = P(n) + 3S(n)

P(n) is the Manhattan Distance of each tile from its proper position.

S(n) is the

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