hill climb

initial([8,1,3,7,0,2,6,5,4]). 
goal([1,2,3,8,0,4,7,6,5]). 
operators([left, right, up, down]). 
% main procedure for breadth first search 
bfs(Start,Path) :-
bfs_path([node(Start,[])], Path). 
% breadth_first search 
bfs_path([node(State,Path) | _], Path) :-
goal(State). 
bfs_path([node(State, Path) | Queue], GoalPath) :-
findall(node(Child,PathToChild), 
( 
apply(Operator, State, Child), 
append(Path,[Operator],PathToChild) 
), ChildNodes), 
append(Queue, ChildNodes, NewQueue), 
bfs_path(NewQueue, GoalPath).
% move_left in the top row 
move_left([X1,0,X3, X4,X5,X6, X7,X8,X9], 
[0,X1,X3, X4,X5,X6, X7,X8,X9]). 
move_left([X1,X2,0, X4,X5,X6, X7,X8,X9], 
[X1,0,X2, X4,X5,X6, X7,X8,X9]). 
% move_left in the middle row 
move_left([X1,X2,X3, X4,0,X6, X7,X8,X9], 
[X1,X2,X3, 0,X4,X6, X7,X8,X9]). 
move_left([X1,X2,X3, X4,X5,0, X7,X8,X9], 
[X1,X2,X3, X4,0,X5, X7,X8,X9]). 
% move_left in the bottom row 
move_left([X1,X2,X3, X4,X5,X6, X7,0,X9], 
[X1,X2,X3, X4,X5,X6, 0,X7,X9]). 
move_left([X1,X2,X3, X4,X5,X6, X7,X8,0], 
[X1,X2,X3, X4,X5,X6, X7,0,X8]). 
% move_right in the top row 
move_right([0,X2,X3, X4,X5,X6, X7,X8,X9], 
[X2,0,X3, X4,X5,X6, X7,X8,X9]). 
move_right([X1,0,X3, X4,X5,X6, X7,X8,X9], 
[X1,X3,0, X4,X5,X6, X7,X8,X9]). 
% move_right in the middle row 
move_right([X1,X2,X3, 0,X5,X6, X7,X8,X9], 
[X1,X2,X3, X5,0,X6, X7,X8,X9]). 
move_right([X1,X2,X3, X4,0,X6, X7,X8,X9], 
[X1,X2,X3, X4,X6,0, X7,X8,X9]). 
% move_right in the bottom row 
move_right([X1,X2,X3, X4,X5,X6, 0,X8,X9], 
[X1,X2,X3, X4,X5,X6, X8,0,X9]). 
move_right([X1,X2,X3, X4,X5,X6, X7,0,X9], 
[X1,X2,X3, X4,X5,X6, X7,X9,0]). 
% move_up from the middle row 
move_up([X1,X2,X3, 0,X5,X6, X7,X8,X9], 
[0,X2,X3, X1,X5,X6, X7,X8,X9]).
move_up([X1,X2,X3, X4,0,X6, X7,X8,X9], 
[X1,0,X3, X4,X2,X6, X7,X8,X9]). 
move_up([X1,X2,X3, X4,X5,0, X7,X8,X9], 
[X1,X2,0, X4,X5,X3, X7,X8,X9]). 
% move_up from the bottom row 
move_up([X1,X2,X3, X4,X5,X6, 0,X8,X9], 
[X1,X2,X3, 0,X5,X6, X4,X8,X9]). 
move_up([X1,X2,X3, X4,X5,X6, X7,0,X9], 
[X1,X2,X3, X4,0,X6, X7,X5,X9]). 
move_up([X1,X2,X3, X4,X5,X6, X7,X8,0], 
[X1,X2,X3, X4,X5,0, X7,X8,X6]). 
% move_down from the top row 
move_down([0,X2,X3, X4,X5,X6, X7,X8,X9], 
[X4,X2,X3, 0,X5,X6, X7,X8,X9]). 
move_down([X1,0,X3, X4,X5,X6, X7,X8,X9], 
[X1,X5,X3, X4,0,X6, X7,X8,X9]). 
move_down([X1,X2,0, X4,X5,X6, X7,X8,X9], 
[X1,X2,X6, X4,X5,0, X7,X8,X9]). 
% move_down from the middle row 
move_down([X1,X2,X3, 0,X5,X6, X7,X8,X9], 
[X1,X2,X3, X7,X5,X6, 0,X8,X9]). 
move_down([X1,X2,X3, X4,0,X6, X7,X8,X9], 
[X1,X2,X3, X4,X8,X6, X7,0,X9]). 
move_down([X1,X2,X3, X4,X5,0, X7,X8,X9], 
[X1,X2,X3, X4,X5,X9, X7,X8,0]). 
% Applying an operator 
apply(left,S1,S2) :- move_left(S1,S2). 
apply(right,S1,S2) :- move_right(S1,S2). 
apply(up,S1,S2) :- move_up(S1,S2). 
apply(down,S1,S2) :- move_down(S1,S2).
%====================================================== 
%Implementation of 8-Puzzle Heuristic Functions 
%====================================================== 
% displacement heuristic 
displaced(State, Number) :-
goal(Goal), 
misplaced(State,Goal,Number). 
% misplaced returns the number of tiles found in the 
% wrong position 
misplaced([],[],0). 
misplaced([0|T1],[0|T2],Number) :- !, 
misplaced(T1,T2,Number). 
misplaced([H|T1],[H|T2],Number) :- !, 
misplaced(T1,T2,Number). 
misplaced([H1|T1],[H2|T2],Number) :- !, 
H1\==H2, 
misplaced(T1,T2,N), 
Number is N+1.
% Manhattan Distance heuristic 
manhattan(State, Number) :-
manh(State,State,0,Number). 
manh([], _, X, X). 
manh([H|T], State, Acc, Result) :-
nth1(Position, State, H), 
NewPos is Position - 1, 
Xaux1 is NewPos mod 3, 
X1 is integer(Xaux1), 
Y1 is NewPos // 3, 
goal(Goal), 
nth1(GoalPosition, Goal, H), 
NewGPos is GoalPosition - 1, 
Xaux2 is NewGPos mod 3, 
X2 is integer(Xaux2), 
Y2 is NewGPos // 3, 
S1 is abs(X1-X2), 
S2 is abs(Y1-Y2), 
N is S1+S2, 
NewAcc is Acc+N, 
manh(T, State, NewAcc, Result).
Output: 
bfs([8,1,3,7,0,2,6,5,4],P).
P = [right, down, left, left, up, up, right, down]