%Proplem implementation :
state(node(State,_,_),State).
action(node(_,Action,_),Action).
cost(node(_,_,Cost),Cost).
initial_node(node([],start,0)).% initial node has empty state
solution(S):- length(S,8).% the search stops after adding 8 queens
%%
%% next:
next(node(S,_,Cost),node([C|S],next,NewCost)):-
	       next_state(S,[C|S]),      
	       NewCost is Cost+1.      


next_state(S,[C|S]):- member(C,[1,2,3,4,5,6,7,8]), 
      	\+ member(C,S), %to avoid more than one queen in the same column
       	 safe_state([C|S]). %the new queen must be compatible with the formers

safe_state([C|S]):- length(S,L),
       Sum is C+L+1, Diff is C-L-1,%C is the column num and L+1 is the row num
       safe_state(S,Sum,Diff).
safe_state([],_,_):-!.
safe_state([F|R],Sm,Df):-length(R,L),
                         X is F+L+1,
	                 X \= Sm,
	                 Y is F-L-1,
	                 Y \= Df,
	                 safe_state(R,Sm,Df).

%General Search Algorithm :
search:- initial_node(Node),
	solve([[Node]],[],Sol),
	reverse(Sol,Solution),
	show(Solution).

solve([Path|_],_,Path):- node(Path,Node),
	state(Node,State),
	solution(State).

solve([Path|Open],Closed,Solution):- node(Path,Node),
	state(Node,State),
	\+ member(State,Closed),!,
	expand(Path,Newstates),
	insert_all(Newstates,Open,NewOpen),
	solve(NewOpen,[State|Closed],Solution).

solve([_|Open],Closed,Solution):- solve(Open,Closed,Solution).

expand(Path,NewPaths):- node(Path,Node),
	findall([NewNode|Path],next(Node,NewNode),NewPaths).

node([Node|_],Node).
%%	
%Outputs 
show([]):- nl.
show([Node|Rest]):- state(Node,S),
	action(Node,A),
	cost(Node,F),
	write(S),write(' '),
	write(A),write(' '),
	write(F),write(' '),
	nl,
	show(Rest).
%%	
% Breadth_first search:
 insert_all(NewStates,Fringe,NewFringe):-
 append(Fringe,NewStates,NewFringe).
% %