Eliminating interchangeable Values in Constraint Satisfaction Problems

Constraint satisfaction problems (CSPs) involve finding values for variables subject to constraints on which combinations of values are permitted. This paper develops a concept of interchangeability of CSP values. Fully interchangeable values can be substituted for one another in solutions to the problem. Removing all but one of a set of fully interchangeable values can simplify the search space for the problem without effectively losing solutions. Refinements of the interchangeability concept extend its applicability. Basic properties of interchangeablity and complexity parameters are established. A hierarchy of local interchangeability is defined that permits recognition of some interchangeable values with polynomial time local computation. Computing local interchangeability at any level in this hierarchy to remove values before backtrack search is guaranteed to be cost effective for some CSPs. Several forms of weak interchangeability are defined that permit eliminating values without losing all solutions. Interchangeability can be introduced by grouping values or variables, and can be recalculated dynamically during search. The idea of interchangeability can be abstracted to encompass any means of recovering the solutions involving one value from the solutions involving another.