Nilsson's sequence score for 8-puzzle problem in A* algorithm

Question

I am learning the A* search algorithm on an 8-puzzle problem.

I don't have questions about A*, but I have some for the heuristic score - Nilsson's sequence score.

Justin Heyes-Jones web pages - A* Algorithm explains A* very clearly. It has a picture for Nilsson's sequence scores.

Nilsson's sequence scores

It explains:

Nilsson's sequence score

A tile in the center scores 1 (since it should be empty)

For each tile not in the center, if the tile clockwise to it is not the one that should be clockwise to it then score 2.

Multiply this sequence by three and finally add the total distance you need to move each tile back to its correct position.

I can't understand the steps above for calculating the scores.

For example, for the start state, what h = 17?

0 A C

H B D

G F E

So, by following the description,

B is in the center, so we have 1

Then for each title not in the center, if the **tile** clockwise to **it** is not the one that should be clockwise to it then score 2. I am not sure what this statement means.

What does the double starred title refer to?

What does the double starred it refer to?

Does the double starred it refer to the center title (B in this example)? Or does it refer to each title not in the center?

Is the next step that we start from A? So C should not be clockwise to A, then we have 2. And then B should be clockwise to A, then we ignore, and so on and so forth?

Answer 1

See if this explanation can help you:

Current pos: Goal:
*AC ABC
HBD H*D
GFE GFE

How to calculate the score:

Center

B in the center -> 1

Distances (manhattan distance)

A must move LEFT -> 1
B must move UP -> 1
sum of distances = 2

Successors (clockwise)

current: ACDEFGH* (skip B because it is in the center)
goal: ABCDEFGH
the [tile,tile clockwise to it] pairs are:
[A,C], [C,D], [D,E], [E,F], [F,G], [G,H], [H,*]
([*,A] is not considered)
the "goal" pairs are:
[A,B], [B,C], [C,D], [D,E], [E,F], [F,G], [G,H], [H,A]

There are 2 pairs that do not match the goal pairs:

[A,C], [H,*]

So the final score is: $distances + 3*(center + 2*successors) = 2 + 3 * (1 + 2*2) = 17$