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.

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, */
  \+ 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),
  \+ member(Posn1, History),
  bounded_depth_first(Depth, [Posn1,Posn|History], Moves).

/* set_flag(Flag) simulates the setting of the global variable Flag.       */
set_flag(Flag):-
  retract(Flag), !, asserta(Flag)
  ;
  asserta(Flag).

/* Test Data */
initial_posn(0).

final_posn(13). 
final_posn(14).  
final_posn(15).

move( 0, 5). move( 0, 6). move( 0, 7). move( 3, 1). move( 4, 2). 
move( 5, 8). move( 6, 9). move( 7,10). move( 8, 3). move( 8, 9). 
move( 9,11). move( 9,12). move( 9,14). move(10, 4). move(10, 9). 
move(11,13). move(11,14). move(12,14). move(12,15).

update(_, Move, State):-State = Move.

legal(_).

LPA Index     Home Page

Valid HTML 4.01 Strict