% Figure 12.10:  An implementation of the IDA* algorithm.

:- op( 900, fy, not).

% not Goal): negation as failure; 
%   Note: This is often available as a built-in predicate,
%   often written as prefix operator "\+", e.g. \+ likes(mary,snakes)

not Goal  :-
  Goal, !, fail
  ; 
  true.

% idastar( Start, Solution):
%   Perform IDA* search; Start is the start node, Solution is solution path

idastar( Start, Solution)  :-
  retract( next_bound(_)), fail     % Clear next_bound
  ;
  asserta( next_bound( 0)),         % Initialise bound
  idastar0( Start, Solution).
  
idastar0( Start, Sol)  :-
  retract( next_bound( Bound)),     % Current bound
  asserta( next_bound( 99999)),     % Initialise next bound
  f( Start, F),                     % f-value of start node
  df( [Start], F, Bound, Sol)       % Find solution; if not, change bound
  ;
  next_bound( NextBound),
  NextBound < 99999,               % Bound finite
  idastar0( Start, Sol).           % Try with new bound

% df( Path, F, Bound, Sol):
%  Perform depth-first search within Bound
%  Path is the path from start node so far (in reverse order)
%  F is the f-value of the current node, i.e. the head of Path

df( [N | Ns], F, Bound, [N | Ns])  :-
  F =< Bound,
  goal( N).                        % Succeed: solution found

df( [N | Ns], F, Bound, Sol)  :-
  F =< Bound,                      % Node N within f-bound
  s( N, N1), not member( N1, Ns),   % Expand N
  f( N1, F1),
  df( [N1,N | Ns], F1, Bound, Sol).

df( _, F, Bound, _)  :-
  F > Bound,                       % Beyond Bound
  update_next_bound( F),           % Just update next bound
  fail.                            % and fail

update_next_bound( F)  :-
  next_bound( Bound),
  Bound =< F, !                      % Do not change next bound
  ;
  retract( next_bound( Bound)), !,   % Lower next bound
  asserta( next_bound( F)).