%move(+CurrentState, -NextState)
% When CurrentState is unified with a state of the puzzle, suceeds when 
% NextState is unified with a state that can be reached in one move

%moves for empty square in top left
move([0,A,B,C,D,E,F,G,H], [A,0,B,C,D,E,F,G,H]).
move([0,A,B,C,D,E,F,G,H], [C,A,B,0,D,E,F,G,H]).

%moves for empty square in top center
move([A,0,B,C,D,E,F,G,H], [0,A,B,C,D,E,F,G,H]).
move([A,0,B,C,D,E,F,G,H], [A,B,0,C,D,E,F,G,H]).
move([A,0,B,C,D,E,F,G,H], [A,D,B,C,0,E,F,G,H]).

%moves for empty square in top right
move([A,B,0,C,D,E,F,G,H], [A,0,B,C,D,E,F,G,H]).
move([A,B,0,C,D,E,F,G,H], [A,B,E,C,D,0,F,G,H]).

%moves for empty square in middle left
move([A,B,C,0,D,E,F,G,H], [0,B,C,A,D,E,F,G,H]).
move([A,B,C,0,D,E,F,G,H], [A,B,C,D,0,E,F,G,H]).
move([A,B,C,0,D,E,F,G,H], [A,B,C,F,D,E,0,G,H]).

%moves for empty square in middle center
move([A,B,C,D,0,E,F,G,H], [A,0,C,D,B,E,F,G,H]).
move([A,B,C,D,0,E,F,G,H], [A,B,C,0,D,E,F,G,H]).
move([A,B,C,D,0,E,F,G,H], [A,B,C,D,E,0,F,G,H]).
move([A,B,C,D,0,E,F,G,H], [A,B,C,D,G,E,F,0,H]).

%moves for empty square in middle right
move([A,B,C,D,E,0,F,G,H], [A,B,0,D,E,C,F,G,H]).
move([A,B,C,D,E,0,F,G,H], [A,B,C,D,0,E,F,G,H]).
move([A,B,C,D,E,0,F,G,H], [A,B,C,D,E,H,F,G,0]).

%moves for empty square in bottom left
move([A,B,C,D,E,F,0,G,H], [A,B,C,0,E,F,D,G,H]).
move([A,B,C,D,E,F,0,G,H], [A,B,C,D,E,F,G,0,H]).

%moves for empty square in bottom center
move([A,B,C,D,E,F,G,0,H], [A,B,C,D,E,F,0,G,H]).
move([A,B,C,D,E,F,G,0,H], [A,B,C,D,0,F,G,E,H]).
move([A,B,C,D,E,F,G,0,H], [A,B,C,D,E,F,G,H,0]).

%moves for empty square in bottom right
move([A,B,C,D,E,F,G,H,0], [A,B,C,D,E,F,G,0,H]).
move([A,B,C,D,E,F,G,H,0], [A,B,C,D,E,0,G,H,F]).

%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
%solved(+Path)
%Succeeds when the last state visited in Path is the goal state for the 8puzzle
solved([1,2,3,4,5,6,7,8,0|R]) :-
	   !.

%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
%possibleMoves(+CurrentState, -MoveList)
%When CurrentBoard is unified with a state for the puzzle, MoveList is unified
%With the list containing all possible states that can be reached in one move

possibleMoves(CurrentState, MoveList) :-
bagof(State, move(CurrentState, State), MoveList).

%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
%removeCycles(+Moves, +Closed, -CycleFreeMoves)
removeCycles([], _, []).
	
removeCycles([X|R], Closed, CycleFreeMoves) :-
	member(X, Closed), !,
	removeCycles(R, Closed, CycleFreeMoves).
	   
removeCycles([X|R], Closed, [X|CycleFreeMoves]) :-
	removeCycles(R, Closed, CycleFreeMoves).
	
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
%sizeOf(+List, -Elements)
%When List is a list elements is unified with the number of elements in that list
sizeOf([], 0).
	   
sizeOf([X|R], Elements) :-
	sizeOf(R, NewElements),
	Elements is NewElements + 1.
	   
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
%updateOpenList(+CycleFreeMoves, +CurrentPath, +Front, -NewOpenList)
%updateOpenList([], CurrentPath, Front, Front) :-
%	!.

%updateOpenList([Move|R], CurrentPath, [], NewOpenList) :-
%updateOpenList(R, CurrentPath, [Move|CurrentPath], NewOpenList).

%updateOpenList([Move|R], CurrentPath, Front, NewOpenList) :-
%		append(Front, [[Move|CurrentPath]], NewFront),
%	   updateOpenList(R, CurrentPath, NewFront, NewOpenList). 

updateOpenList([],_,Rest,Rest).

updateOpenList([Next|Cycle_Free],Current,Rest,NewPath) :- 
append(Path,[[Next|Current]],NewPath),
updateOpenList(Cycle_Free,Current,Rest,Path).
	   
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
%out_of_place(+CurrentState, -Number)
%When CurrentState is unified with the current state of the puzzle
%Number gets unified with the number of tiles out of place.

out_of_place(CurrentState, Number) :-
	out_of_place(CurrentState, [1,2,3,4,5,6,7,8,0], Number).

%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
%out_of_place(+CurrentState, +GoalState, -Number)
%When CurrentState is unified with the current state of the puzzle, and
%GoalState is unified with the goal state for the puzzle, Number is unified with 
%the number of tiles that are out of place

out_of_place([], [], 0) :- 
	!.

out_of_place([X|R1], [X|R2], Number) :-
	!, out_of_place(R1, R2, Number).

out_of_place([X|R1], [Y|R2], PlusOne) :-
	out_of_place(R1, R2, Number),
	PlusOne is Number + 1.
	
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

printResults([]).

printResults([X|R] ) :-
	printResults(R),
	printState(X).
	
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

printState([]) :-
	nl.
printState([X|[]]) :-
	write(X),
	printState([]).
	
printState([X|R]) :-
	write(X), write(', '),
	printState(R).