You also need to define four procedures, as follows:
is_goal_state(state, goal) -> booleanThis is given a state, and a specification of the current goal and returns true if the state is acceptable as a goal state, otherwise false. This procedure will be different for different sorts of problems.
next_states(state) -> newstates;The procedure next_states is given a state and returns a list of states that can be reached in one step from that state. The procedure will be have to be defined differently for different problems.
same_state(state1, state2) -> booleanThis procedure is required so that the problem solver can tell whether a particular new state is equivalent to one that has previously been examined, so that time is not wasted examining it again and trying to explore its successors. Since the notion of equivalence will depend on the kind of problem and how states are represented, this has to be defined by the user.
If this procedure is provided, then the general problem solver can keep a "history" list of the states that have already been examined, and whenever new states are generated it can discard any of them that are "the same" as a state already on the history list.
insert_state(state, oldstates) -> newstatesThis procedure can embody some "heuristic" information. It is given a new state (e.g. something produced by the procedure next_states) and list of states waiting to be explored, and it returns a new list of states, with an order which represents the best current guess as to which one should be examined first. For example it is often useful to prune a search space by working first on items that are going to be most difficult to fit into a complete solution, so that those that are unusable are quickly eliminated from further combinations of items.
The problem solver described below needs this utility procedure which can be applied to a state, a list of states, and the user's procedure same_state, to check whether the first state is equivalent to one of those in the list. It returns a true or false result.
define is_in_list(newitem, list, sameitem) -> boole;
;;; Return true if and only if the newitem is the same as something in
;;; in the list, as compared using the procedure sameitem
lvars procedure sameitem; ;;; declare it as a procedure, for speed
lvars olditem;
for olditem in list do
if sameitem(newitem, olditem) then
;;; found an olditem which is the same, so return with true
true -> boole;
return();
endif
endfor;
;;; did not find anything that was the same
false -> boole
enddefine;