Non-deterministic computing

This computing paradigm is particularly useful for problems of constraint-satisfaction where many solutions are possible, and any are satisfactory. The idea is to implement the notion of non-deterministic choice points which can be backtracked to if the subsequent evaluation fails the constraint, so that a different choice can be tried out.

Practically, this requires support for expressions that have ambiguous return values that the evaluator can choose (by backtracking) based on other conditions. In Lisp, the amb evaluator provides this support. The statement

(amb <e1> <e2> .. <en>)

returns one of the n expressions <ei> ambiguously.

The backtracking could implement any sort of search strategy. The simplest is depth-first search by using chronological backtracking, i. e, going back to the most recent branch point, and picking an alternative choice. Modern problem-solving systems use something called a truth-maintenance strategy based on dependency-directed backtracking that is more sophisticated and efficient.