A Sufficient Condition for Backtrack-Free Search
Eugene C. Freuder · Journal of the ACM · 1982
A constraint satisfaction problem revolves 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 mimmum backtracking (none) The relationship involves a concept called "width," which may provide some guidance in the representation of constraint satisfaction problems and the order m which they are searched The width concept is studied and applied, in particular, to constraints which form tree structures.