A Sufficient Condition for Backtrack-Free Search

A constraint satisfaction problem involves finding values for a set of variables subject to a set of constraints (relations) on those variables. Backtrack search is often used to solve such problems. A relationship involving the structure of the constraints is described which characterizes to some degree the extreme case of minimum backtracking (none). The relationship involves a concept called “width,” which may provide some guidance in the representation of constraint satisfaction problems and the order in which they are searched. The width concept is studied and applied, in particular, to constraints which form tree structures.