This is a framework for an A* search inspired by the other similar search frameworks given in Sterling and Shapiro's "The Art of Prolog".
astar(Moves):- initial_posn(Position), astar_1([s(Position, [], 0)], [], Moves). /* astar_1(States, History, Moves) is true if Moves is a sequence of */ /* moves to reach a desired final state from the initial state, where */ /* States contains the current states under consideration, and History */ /* contains the positions visited previously. */ astar_1([s(Posn, Path, _)|_], _, Moves):- final_posn(Posn), reverse(Path, Moves). astar_1([s(Posn, Path, Value)|States], History, FinalMoves):- findall(Move, move(Posn, Move), Moves), filter(Moves, s(Posn, Path, Value), History, States, States1), astar_1(States1, [Posn|History], FinalMoves). filter([], _, _, States, States). filter([Move|Moves], s(Posn, Path, Value0), History, States, States1):- update(Posn, Move, Posn1), legal(Posn1), \+ member(Posn1, History), !, value(Posn1, I), length(Path, J), Value1 is I + J, insert(States, s(Posn1, [Move|Path], Value1), States0), filter(Moves, s(Posn, Path, Value0), History, States0, States1). filter([_|Moves], State, History, States, States1):- filter(Moves, State, History, States, States1). insert([s(P2, M2, V2)|States0], s(P1, M1, V1), States):- V1 > V2, !, States = [s(P2, M2, V2)|States1], insert(States0, s(P1, M1, V1), States1). insert(States, State, [State|States]). /* * Test Data - This is Exercise 18.1 (ii) from "The Art of Prolog" * by Sterling and Shapiro */ /* p(WhereTheBoatIs, MissionariesOnLeft, CannibalsOnLeft) */ /* m(MissionariesInBoat, CannibalsInBoat) */ initial_posn(p(left, 3, 3)). final_posn(p(right, 0, 0)). move(p(left, M, _), m(1, 0)):-M >= 1. move(p(left, _, C), m(0, 1)):-C >= 1. move(p(left, M, C), m(1, 1)):-M >= 1, C >= 1. move(p(left, M, _), m(2, 0)):-M >= 2. move(p(left, _, C), m(0, 2)):-C >= 2. move(p(right, M, _), m(1, 0)):-(3 - M) >= 1. move(p(right, _, C), m(0, 1)):-(3 - C) >= 1. move(p(right, M, C), m(1, 1)):-(3 - M) >= 1, (3 - C) >= 1. move(p(right, M, _), m(2, 0)):-(3 - M) >= 2. move(p(right, _, C), m(0, 2)):-(3 - C) >= 2. update(p(left, M0, C0), m(MB, CB), p(right, M, C)):- M is M0 - MB, C is C0 - CB. update(p(right, M0, C0), m(MB, CB), p(left, M, C)):- M is M0 + MB, C is C0 + CB. /* This uses an (under)estimation of the number of remaining voyages as */ /* the evaluation function. */ value(p(_, M, C), 1):-M + C =:= 1, !. value(p(left, M, C), L):-L is (M + C - 2) * 2 + 1. value(p(right, M, C), L):-L is (M + C) * 2. /* Ensures that, on each bank, the cannibals are not outnumbered */ legal(p(_, _, 3)):-!. legal(p(_, _, 0)):-!. legal(p(_, M, M)).