/*
solve_best(Frontier,History,Moves) :-
Moves is the sequence of moves to reach a desired final state
from the initial state. Frontier contains the current states
under consideration. History contains the states visited previously.
*/
:- op(900,fy,not).
solve_best([state(State,Path,Value)|Frontier],History,Moves) :-
final_state(State), reverse(Path,[],Moves).
solve_best([state(State,Path,Value)|Frontier],History,FinalPath) :-
findall(M,move(State,M),Moves),
update_frontier(Moves,State,Path,History,Frontier,Frontier1),
solve_best(Frontier1,[State|History],FinalPath).
update_frontier([Move|Moves],State,Path,History,Frontier,Frontier1) :-
update(State,Move,State1),
legal(State1),
value(State1,Value),
not member(State1,History),
insert(state(State1,[Move|Path],Value),Frontier,Frontier0),
update_frontier(Moves,State,Path,History,Frontier0,Frontier1).
update_frontier([],State,Path,History,Frontier,Frontier).
insert(State,[],[State]).
insert(State,[State1|States],[State,State1|States]) :-
lesseq_value(State,State1).
insert(State,[State1|States],[State|States]) :-
equals(State,State1).
insert(State,[State1|States],[State1|States1]) :-
greater_value(State,State1), insert(State,States,States1).
equals(state(S,P,V),state(S,P1,V)).
lesseq_value(state(S1,P1,V1),state(S2,P2,V2)) :- S1 \== S2, V1 =< V2.
greater_value(state(S1,P1,V1),state(S2,P2,V2)) :- V1 > V2.
reverse([X|Xs],Acc,Ys) :- reverse(Xs,[X|Acc],Ys).
reverse([],Ys,Ys).
% Program 20.7 Concise best first framework for problem solving