The first description of a generalized backtrack search algorithm was in
[35]. Let us first define a restricted version of the search
problem.
Search problem:
Given a collection of sets of candidates and
a boolean compatibility function defined for all and , find an m-tuple with such that is true for all .
The m-tuple satisfying the above condition is called a solution.
The term compatibility was first introduced by Carter in 1974
[9]. This version is restricted because the compatibility
function is only defined on ordered pairs rather than on all k-tuples,
.
Annotation Form Interface