A Sufficient Condition for Backtrack-Free Search

Abstract

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.