A* search in 8-puzzle prolog

Question

I need to create program in prolog that solves the 8-puzzle game, I already figured out the moves and have some code on the search, but I don't know how to implement the heuristic in the search(informed search).

The State is represented in a list-of-list structure, like: [[2,8,3],[1,6,4],[7,0,5]], and the heuristic is the amount of numbers(tiles) not in his desired position([[1,2,3],[8,0,4],[7,6,5]]). The code for the heuristic:

line_matching([], [], []).
line_matching([X|Y], [X|Z], S):- line_matching(Y, Z, S).
line_matching([X|Y], [W|Z], [X|K]):- line_matching(Y, Z, K).


list_count([], 0).
list_count([X|Y], R):- list_count(Y, R2), R is R2 + 1.


wrong_position(Line, 1, Y):- line_matching(Line, [1, 2, 3], Z), list_count(Z,Y).
wrong_position(Line, 2, Y):- line_matching(Line, [8, 0, 4], Z), list_count(Z,Y).
wrong_position(Line, 3, Y):- line_matching(Line, [7, 6, 5], Z), list_count(Z,Y).

heuristic_count([X, Y, Z], H):- wrong_position(X, 1, R1), wrong_position(Y, 2, R2),
    wrong_position(Z, 3, R3), H is (R1 + R2 + R3).

In addition to this heuristic, I need to calculate the cost to get to the goal State, which I'm also having some trouble.

For the search, I have this:

% left/right movements

lr([[0,A,B], L2, L3], [[A,0,B], L2, L3]).
lr([[A,0,B], L2, L3], [[A,B,0], L2, L3]).
lr([L1, [0,A,B], L3], [L1, [A,0,B], L3]).
lr([L1, [A,0,B], L3], [L1, [A,B,0], L3]).
lr([L1, L2, [0,A,B]], [L1, L2, [A,0,B]]).
lr([L1, L2, [A,0,B]], [L1, L2, [A,B,0]]).

% up/down movements

ud([[0,A,B], [C,D,E], L3], [[C,A,B], [0,D,E], L3]).
ud([[A,0,B], [C,D,E], L3], [[A,D,B], [C,0,E], L3]).
ud([[A,B,0], [C,D,E], L3], [[A,B,E], [C,D,0], L3]).
ud([L1, [0,A,B], [C,D,E]], [L1, [C,A,B], [0,D,E]]).
ud([L1, [A,0,B], [C,D,E]], [L1, [A,D,B], [C,0,E]]).
ud([L1, [A,B,0], [C,D,E]], [L1, [A,B,E], [C,D,0]]).

% all movements

mv(rt, Old, New) :- lr(Old, New).
mv(lt, Old, New) :- lr(New, Old).
mv(up, Old, New) :- ud(New, Old).
mv(dn, Old, New) :- ud(Old, New).
           

% depth first search

dfs(PresentState,GoalState,SolutionPath) :- 
    dfs1(PresentState,GoalState,[PresentState],SolutionPath).
  
  % base case
dfs1(PresentState,Goalstate,PathSoFar,SolutionPath) :- 
     Goalstate=PresentState,
     reverse(PathSoFar,SolutionPath).
  
  % recursive case
dfs1(PresentState, GoalState, PathSoFar, Path) :- 
    mv(_, PresentState,Next),
    not(member(Next, PathSoFar)),
    length(PathSoFar, D), D=<15,
    dfs1(Next,GoalState,[Next|PathSoFar],Path).
   

The only thing that keeps the SolutionPath short is the length restriction that I put.

I'm trying to sort the 'path so far' list based on the heuristic, or something like that. I've tried to create another predicate to sort a list based on another predicate using findall, but no success.

Thanks in advance.