The evaluation function of this question is f(x) = g(x) + h(x), where g(x) is the depth of node x, h(x) is the manhattan distance between all chess and the goal (sum of the vertical and horizontal distances of the chess between the goal). For example, the depth of nodes in start status (S0) = 0, for number 2 in start status (S0), the manhattan distance h(x) of number 2 is 1, because from start status to goal status, 2 has to move 1 step horizontally. Another example, for number 8 in start status (S0), the manhattan distance h(x) of number 8 is 2 (1 in horizontal + 1 in the vertical direction = 2 in total).

8 3 Start status (SO):| 1 | 6 | 4 Goal status : 8 3 Start status (SO):| 1 | 6 | 4 Goal status