My Diversions

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).