The previous Module used a simple network to show how to write rules to
traverse this network. This Module introduces a small change to the network
to introduce non-determinism. This allows Prolog's search mechanism to
be revealed in greater detail, which in turn allows a closer examination
of the technique of recursion.
The network used in Module 3 was deterministic in the sense that there
are no dead ends. However, if there is a break in the network, it is possible
to find routes that lead to dead ends. Prolog has a way of recovering from
dead ends and finding alternative solutions. Prolog's ability of cope with
non-determinism is one of its strengths.
It follows that if it is possible for Prolog to cope with non-deterministic
situations, it is easy for it to deal with situations where there is more
than one solution.
Prolog's non-determinism is made possible by the use of a stack data structure
to store alternative "paths" (or partial solutions). By the use of the
stack, Prolog displays the symptom of backtracking.
