This is a framework for an A* with Iterative Deepening (IDA*) search, inspired by the other similar search frameworks given in Sterling and Shapiro's "The Art of Prolog".
Only one solution is found.
A more efficient version is obtained if, instead of incrementing Limit by 1 in idastar_1/4, the minimum value of F when F exceeds Limit in idastar_2/6 is used for the new value of Limit. This is left as an exercise for the reader!
idastar(Moves):- initial_posn(Position), value(Position, H), idastar_1(Position, H, H, Moves), !. idastar_1(Position, F, Limit, Moves):- idastar_2([Position], 0, F, Limit, Moves). idastar_1(Position, F, Limit, Moves):- Limit1 is Limit + 1, idastar_1(Position, F, Limit1, Moves). idastar_2([Position|_], _, _, _, []):- final_posn(Position), !. idastar_2(Positions0, G, F, Limit, [Move|Moves]):- Positions0 = [Position|Positions], F =< Limit, move(Position, Move), update(Position, Move, Position1), legal(Position1), \+ member(Position1, Positions), value(Position1, H1), G1 is G + 1, F1 is G1 + H1, idastar_2([Position1|Positions0], G1, F1, Limit, Moves). /* * Test data * Five Jealous Husbands - Sterling and Shapiro - Exercise 18.1 (iii) * Goal: idastar(Moves). */ /* p(WhereTheBoatIs, PeopleOnIsle, PeopleOnBank) */ initial_posn(p(isle, [h1,h2,h3,h4,h5,w1,w2,w3,w4,w5], [])). % initial_posn(p(isle, [h1,h2,h3,h4,w1,w2,w3,w4], [])). % initial_posn(p(isle, [h1,h2,h3,w1,w2,w3], [])). final_posn(p(bank, [], _)). move(p(isle, I, _), [P1]):- /* Move one person from isle to bank */ member(P1, I). move(p(isle, I, _), [P1,P2]):- /* Move two people from isle to bank */ rest(I, P1, I1), member(P2, I1), legal_1([P1,P2]). move(p(isle, I, _), [P1,P2,P3]):- /* Move three people from isle to bank */ rest(I, P1, I1), rest(I1, P2, I2), member(P3, I2), legal_1([P1,P2,P3]). move(p(bank, _, B), [P1]):- /* Move one person from bank to isle */ member(P1, B). move(p(bank, _, B), [P1,P2]):- /* Move two people from bank to isle */ rest(B, P1, B1), member(P2, B1), legal_1([P1,P2]). move(p(bank, _, B), [P1,P2,P3]):- /* Move three people from bank to isle */ rest(B, P1, B1), rest(B1, P2, B2), member(P3, B2), legal_1([P1,P2,P3]). update(p(isle, I1, B1), Boat, p(bank, I2, B2)):- ord_delete(Boat, I1, I2), ord_insert(Boat, B1, B2). update(p(bank, I1, B1), Boat, p(isle, I2, B2)):- ord_delete(Boat, B1, B2), ord_insert(Boat, I1, I2). /* This uses a crude (under)estimation of the number of remaining voyages */ /* as the evaluation function. */ value(p(isle, Xs, _), L):-length(Xs, M), L is (M // 2) * 2 - 1. value(p(bank, Xs, _), L):-length(Xs, M), L is (M + 1) // 2 * 2. legal(p(_, Xs, Ys)):-legal_1(Xs), legal_1(Ys). legal_1(Xs):-only_wives(Xs), !. legal_1(Xs):-wives_with_husbands(Xs, Xs). only_wives([]). only_wives([W|Xs]):-couple(_, W), only_wives(Xs). wives_with_husbands([], _). wives_with_husbands([H|Xs], Ys):- couple(H, _), !, wives_with_husbands(Xs, Ys). wives_with_husbands([W|Xs], Ys):- couple(H, W), member(H, Ys), wives_with_husbands(Xs, Ys). couple(h1, w1). couple(h2, w2). couple(h3, w3). couple(h4, w4). couple(h5, w5). /* ord_delete(Xs, Ys, Zs) is true if Zs is the ordered list obtained */ /* by deleting the ordered list Xs from the ordered list Ys. */ ord_delete([], Ys, Ys). ord_delete([X|Xs], [X|Ys], Zs):- !, ord_delete(Xs, Ys, Zs). ord_delete([X|Xs], [Y|Ys], Zs):- X @> Y, !, Zs = [Y|Ws], ord_delete([X|Xs], Ys, Ws). ord_delete([_|Xs], Ys, Zs):- ord_delete(Xs, Ys, Zs). /* ord_insert(Xs, Ys, Zs) is true if Zs is the ordered list obtained */ /* by inserting the ordered list Xs in the ordered list Ys. */ ord_insert([], Ys, Ys). ord_insert([X|Xs], [Y|Ys], Zs):- Y @=< X, !, Zs = [Y|Ws], ord_insert([X|Xs], Ys, Ws). ord_insert([X|Xs], Ys, [X|Zs]):- ord_insert(Xs, Ys, Zs). /* rest(Xs, Y, Zs) is true if Zs is the list of elements following the */ /* element Y in the list Xs. */ rest([X|Xs], X, Xs). rest([_|Xs], Y, Zs):-rest(Xs, Y, Zs).