And the first find when query the agenda facts

http://www.cs.nps.navy.mil/people/faculty/rowe/book/chap10.html

be found for this earlier state, it is then taken. Otherwise, this invocation of the rule also fails, and backing up and backtracking happens again.

successor(b,c).

successor(a,d).

Assume for this problem that the starting state is a, and there is only one goal state e. Then the problem-definition file must also include

goalreached(e).

2. The goal is not reached in state a, so the second rule for depthsearch2 is tried.

3. In the successor facts, the first successor of state a is b, and b is not a member of the list of previous states, [a]. So depthsearch2 is recursively called with first argument b, second argument [b,a], and third argument unbound.

rules for depthsearch2 fail. We must backtrack, "backing up" to the previous state b at the second level, and hence to the recursive depthsearch2 call in the last line of the last depthsearch2 rule.

6. The not fails on backtracking, as all nots do, so we backtrack further to the successor predicate in the second rule for depthsearch2, which chooses successors. Backtracking to here means we want a different successor for state b than c. And the only other successor of b is d. So we resume forward progress through the second depthsearch2 rule with Newstate bound to d. This d is not in the list of previously visited states [b,a], so we recursively call depthsearch2 with first argument d, second argument [d,b,a] (c was removed in backtracking), and third argument unbound.

Notice this is not the shortest solution to the problem, as is common with depth-first search.

Implementing breadth-first search