%   File   : /usr/lib/prolog/search/guess_first
%   Author : R.A.O'Keefe
%   Updated: 21 December 1983
%   Purpose: define a schema for guess first search

%   This schema has five parameters:
%	starting_position(Start)
%		binds Start to the first position to try
%	solution(Position)
%		tests whether a Position is a solution or not
%	operator_applies(Operator, OldPosition, NewPosition)
%		enumerates all the operators which apply to the
%		OldPosition, and also gives the NewPosition which
%		results from that operator application.
%	equivalent(Pos1, Pos2)
%		tests whether the two positions are essentially
%		the same.  The idea is that we will only look at
%		a position once.
%	distance(Position, Distance)
%		returns an estimate of how far the Position is
%		from a solution.  This is only used to rank the
%		descendants of a node, so the actual values of
%		the estimate don't matter too much.  See BEST
%		for a method where the values *do* matter.

%   guess_first_search(Position, OperatorList)
%	returns the first solution it can find, and the list of
%	Operators which produced it: [O1,...,On] means that
%	applying O1 to the start position, then O2, then ... and
%	finally On produces Position.


guess_first_search(Position, History) :-
	starting_position(Start),
	guess_first_search([Start-[]], [Start], Position, History).


guess_first_search([Position-OpList|_], _, Position, OpList) :-
	solution(Position),
	!.	%  assuming you want only one
guess_first_search([Position-OpList|Rest], Seen, Answer, History) :-
	findall(Operator, new_position(Operator, Position, Seen), Ops),
	%   we can't use setof, because that fails when there is no such Op
	fill_out(Ops, Position, OpList, Seen, NewSeen, Descendants),
	rank(Descendants, ByOrderOfGuess),
	append(ByOrderOfGuess, Rest, NewRest),
	!,
	guess_first_search(NewRest, NewSeen, Answer, History).


new_position(Operator, Position, Seen) :-
	operator_applies(Operator, Position, NewPos),
	\+ (
	    member(OldPos, Seen),
	    equivalent(OldPos, NewPos)
	).


fill_out([], _, _, Seen, Seen, []) :- !.
fill_out([Op|Ops], Position, OpList, Seen, NewSeen, 
		[Distance-(NewPos-[Op|OpList])|New]) :-
	operator_applies(Op, Position, NewPos),
	distance(NewPos, Distance), !,
	fill_out(Ops, Position, OpList, [NewPos|Seen], NewSeen, New).


rank(Keyed, Ranked) :-
	keysort(Keyed, Sorted),
	strip(Sorted, Ranked).

strip([], []) :- !.
strip([_-H|T], [H|R]) :-
	strip(T, R).