Depth First with Iterative Deepening Search

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

Turbo Prolog Index     Home Page