% Figure 13.8: Depth-first search for AND/OR graphs. This program
% does not avoid infinite cycling. Procedure 'solve' finds a solution 
% tree, procedure 'show' displayes such a tree. 'show' assumes that 
% each node on output only takes 1 characetr.


%  Depth-first AND/OR search
%  solve( Node, SolutionTree):
%    find a solution tree for Node in an AND/OR graph

:-  op( 500, xfx, :).
:-  op( 600, xfx, ---> ).


'-xo -o- xx-' ---> or:['oxo -o- xx-', '-xo -o- xxo'].

'oxo -o- xx-' ---> and:['oxo xo- xx-', 'oxo -ox xx-', 'oxo -o- xxx'].
'-xo -o- xxo' ---> and:['xxo -o- xxo', '-xo xo- xxo', '-xo -ox xxo'].

'oxo xo- xx-' ---> or:['oxo xoo xx-', 'oxo xo- xxo'].
'oxo -ox xx-' ---> or:['oxo oox xx-', 'oxo -ox xxo'].
'xxo -o- xxo' ---> or:['xxo oo- xxo', 'xxo -oo xxo'].
'-xo xo- xxo' ---> or:['oxo xo- xxo', '-xo xoo xxo'].
'-xo -ox xxo' ---> or:['oxo -ox xxo', '-xo oox xxo'].

goal('oxo xo- xxo').
goal('oxo -ox xxo').
goal('xxo -oo xxo').
goal('oxo xo- xxo').
goal('-xo xoo xxo').
goal('oxo -ox xxo').



solve( Node, Node, MaxDepth)  :-              % Solution tree of goal node is Node itself
  goal(Node).

solve( Node, Node ---> Tree, MaxDepth)  :-
  MaxDepth > 0,
  Node ---> or:Nodes,               % Node is an OR-node
  member( Node1, Nodes),            % Select a successor Node1 of Node
  Depth1 is MaxDepth - 1,
  solve( Node1, Tree, Depth1).

solve( Node, Node ---> and:Trees, MaxDepth)  :-
  MaxDepth > 0,
  Node ---> and:Nodes,              % Node is an AND-node
  Depth1 is MaxDepth - 1,
  solveall( Nodes, Trees, Depth1).          % Solve all Node's successors

% solveall( [Node1,Node2, ...], [SolutionTree1,SolutionTree2, ...])

solveall( [], [], MaxDepth).

solveall( [Node|Nodes], [Tree|Trees], MaxDepth)  :-
  solve( Node, Tree, MaxDepth),
  solveall( Nodes, Trees, MaxDepth).

%  Displaying a solution tree

show(Tree)  :-                   % Display solution tree
  show(Tree,0), !.               % Indented by 0

% show( Tree, H): display solution tree indented by H

show( Node ---> Tree, H)  :-  !,
  write(Node), write(' ---> '),
  H1 is H + 17,
  show( Tree, H1).

show( and:[T], H)  :-  !,        % Display single AND tree
  show(T,H).

show( and:[T|Ts], H)  :-  !,     % Display AND-list of solution trees
  show( T, H),
  tab(H),
  show( and:Ts, H).

show( Node, H) :-
  write(Node), nl.
  
test1('-xo -o- xx-' ---> K):-
        solve(L,'-xo -o- xx-' ---> K, 5), show('-xo -o- xx-' ---> K).
