#### A* with Iterative Deepening Search

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).
```