The first description of a generalized backtrack search algorithm was in [35]. Let us first define a restricted version of the search problem.

TheSearch problem:

Given a collection of sets of candidates and a booleancompatibilityfunction defined for all and , find anm-tuplewith such that is true for all .