inicial([1,2,3,8,-,4,7,5,6]).
meta(   [-,1,2,3,4,5,6,7,8]).

ação(n, [A,B,C,-,D,E,F,G,H], [-,B,C,A,D,E,F,G,H], 1).
ação(n, [A,B,C,D,-,E,F,G,H], [A,-,C,D,B,E,F,G,H], 1).
ação(n, [A,B,C,D,E,-,F,G,H], [A,B,-,D,E,C,F,G,H], 1).
ação(n, [A,B,C,D,E,F,-,G,H], [A,B,C,-,E,F,D,G,H], 1).
ação(n, [A,B,C,D,E,F,G,-,H], [A,B,C,D,-,F,G,E,H], 1).
ação(n, [A,B,C,D,E,F,G,H,-], [A,B,C,D,E,-,G,H,F], 1).

ação(s, [-,B,C,A,D,E,F,G,H], [A,B,C,-,D,E,F,G,H], 1).
ação(s, [A,-,C,D,B,E,F,G,H], [A,B,C,D,-,E,F,G,H], 1).
ação(s, [A,B,-,D,E,C,F,G,H], [A,B,C,D,E,-,F,G,H], 1).
ação(s, [A,B,C,-,E,F,D,G,H], [A,B,C,D,E,F,-,G,H], 1).
ação(s, [A,B,C,D,-,F,G,E,H], [A,B,C,D,E,F,G,-,H], 1).
ação(s, [A,B,C,D,E,-,G,H,F], [A,B,C,D,E,F,G,H,-], 1).

ação(l, [-,A,B,C,D,E,F,G,H], [A,-,B,C,D,E,F,G,H], 1).
ação(l, [A,-,B,C,D,E,F,G,H], [A,B,-,C,D,E,F,G,H], 1).
ação(l, [A,B,C,-,D,E,F,G,H], [A,B,C,D,-,E,F,G,H], 1).
ação(l, [A,B,C,D,-,E,F,G,H], [A,B,C,D,E,-,F,G,H], 1).
ação(l, [A,B,C,D,E,F,-,G,H], [A,B,C,D,E,F,G,-,H], 1).
ação(l, [A,B,C,D,E,F,G,-,H], [A,B,C,D,E,F,G,H,-], 1).

ação(o, [A,-,B,C,D,E,F,G,H], [-,A,B,C,D,E,F,G,H], 1).
ação(o, [A,B,-,C,D,E,F,G,H], [A,-,B,C,D,E,F,G,H], 1).
ação(o, [A,B,C,D,-,E,F,G,H], [A,B,C,-,D,E,F,G,H], 1).
ação(o, [A,B,C,D,E,-,F,G,H], [A,B,C,D,-,E,F,G,H], 1).
ação(o, [A,B,C,D,E,F,G,-,H], [A,B,C,D,E,F,-,G,H], 1).
ação(o, [A,B,C,D,E,F,G,H,-], [A,B,C,D,E,F,G,-,H], 1).


% manhattan distance

h(S, H) :-
    meta(G),
    aggregate_all(
        sum(D),
        (  nth0(P, S, T),
           T \= '-',
           nth0(Q, G, T),
           D is abs(P div 3 - Q div 3) + abs(P mod 3 - Q mod 3)
         ),
        H).