This is a framework for a Depth First with Iterative Deepening search, inspired by the other similar search frameworks given in Sterling and Shapiro's "The Art of Prolog". All solutions are found, and each solution is reported only once.
/*** The following must be defined by the caller: domains move = posn = database more_nodes predicates initial_posn(posn) final_posn(posn) nondeterm move(posn,move) update(posn,move,posn) legal(posn) ***/ domains moves = move* posns = posn* depth = s(depth) ; zero predicates nondeterm dfid(moves) nondeterm iterative_deepening(depth,posns,moves) nondeterm bounded_depth_first(depth,posns,moves) nondeterm member(posn,posns) set_flag(dbasedom) clauses dfid(Moves):- initial_posn(Posn), set_flag(more_nodes), iterative_deepening(zero, [Posn], Moves). /* iterative_deepening(Depth, [State], Moves) is true if Moves is the */ /* sequence of moves to reach a desired final state from the current */ /* State in at least Depth moves. */ iterative_deepening(_, _, _):- /* If we didn't have this clause, */ not(retract(more_nodes)), !, fail. /* we would never terminate. */ iterative_deepening(Depth, History, Moves):- bounded_depth_first(Depth, History, Moves). iterative_deepening(Depth, History, Moves):- iterative_deepening(s(Depth), History, Moves). /* bounded_depth_first(Depth, [State|History], Moves) is true if Moves is */ /* the sequence of moves to reach a desired final state from the current */ /* State in exactly Depth moves, where History contains the states */ /* visited previously. */ bounded_depth_first(zero, [Posn|_], []):- set_flag(more_nodes), final_posn(Posn). bounded_depth_first(s(Depth), [Posn|History], [Move|Moves]):- move(Posn, Move), update(Posn, Move, Posn1), legal(Posn1), not(member(Posn1, History)), bounded_depth_first(Depth, [Posn1,Posn|History], Moves). /* member(X, Xs) is true if X is a member of the list Xs. */ member(X, [X|_]). member(X, [_|Ys]):-member(X, Ys). /* set_flag(Flag) simulates the setting of the global variable Flag. */ set_flag(Flag):- retract(Flag), !, asserta(Flag) ; asserta(Flag).