The algorithm implemented in my previous post pays no attention to the nodes in the search space already visited, so if the `situation [[c,a,b],[],[]]`

is used as the starting point an infinite recursion will result, as the successor function starts to traverse a cycle in the state space graph before it finds a goal node.

On pages 246 and 247 (figure 11.7) Bratko adds cycle detection:

We can now solve `[[c,a,b],[],[]]`

, but note that the solution is not very efficient:

```
[[[c, a, b], [], []],
[[a, b], [c], []],
[[b], [a, c], []],
[[], [b, a, c], []],
[[a, c], [b], []],
[[c], [a, b], []],
[[], [c], [a, b]],
[[], [c], [a, b]],
[[b], [a], [c]],
[[], [b, a], [c]],
[[a], [b], [c]],
[[], [a, c], [b]],
[[c], [a], [b]],
[[], [c, a], [b]],
[[a], [c], [b]],
[[], [c, b], [a]],
[[b], [c], [a]],
[[], [b, c], [a]],
[[c], [b, a], []],
[[], [c, b, a], []],
[[b, a], [c], []],
[[a], [b, c], []],
[[], [a, b, c], []]]
```

The algorithm doesn’t recognise that the nodes `[[b], [a, c], []]`

and `[[a, c], [b], []]`

, for example, are equivalent.

The code has only minor changes:

```
:- module stacks2.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is cc_multi.
:- implementation.
:- import_module list.
:- import_module bool.
/*
* In Mercury we can use types to represent the problem domain -- a situation
* is a number of stacks of blocks.
*/
:- type block ---> a; b; c.
:- type stack == list(block).
:- type situation == list(stack).
:- type solution == list(situation).
:- pred s(situation, situation).
:- mode s(in,out) is nondet.
/*
* list.delete uses a different order of arguments to the del predicate
* used by bratko: delete(List, Element, Remainder)
*/
s(Stacks, [Stack1, [Top1 | Stack2] | OtherStacks]) :-
delete(Stacks, [Top1 | Stack1], Stacks1),
delete(Stacks1, Stack2, OtherStacks).
:- pred goal(situation::in) is semidet.
goal(Situation) :-
member([a,b,c], Situation).
:- pred solve(situation::in, solution::out) is nondet.
solve(Node, Solution) :-
depthfirst([],Node,Solution).
:- pred depthfirst(solution::in, situation::in, solution::out) is nondet.
depthfirst(Path, Node, [Node | Path]) :- goal(Node).
depthfirst(Path, Node, Sol) :-
s(Node, Node1),
not member(Node1, Path),
depthfirst([Node | Path], Node1, Sol).
/*
* Note that the solution returned by solve starts with the final goal node, so
* we reverse it before printing it.
*/
main(!IO) :-
if solve([[c,a,b],[],[]],S) then
reverse(S,S1), print(S1,!IO)
else
print("Failed\n",!IO).
```