When a constraint satisfaction problem requires or allows user interaction in the course of the solution, it is important that the solver prevent the user from selecting values for which no solution is possible. This might be the case where a user is configuring a car that she wishes to purchase; some models might not be available in a particular color, for example. Since the recomputation of the variable domains can be time consuming, it is desirable that some way be found to manage the solver so as to provide maximal assistance to the user.
In this paper, the authors consider a condition, global inverse consistency (GIC), in which for every variable-value pair (x,a) still under consideration, there is a solution in which the variable x takes the value a. This ensures that all potential values presented to the user belong to some solution. Not surprisingly, deciding whether a constraint network is GIC is NP-complete. However, the authors provide a number of algorithms that can be used to enforce GIC. In addition, they give an algorithm for restoring GIC. This would be required whenever a user makes a selection.
The authors describe a number of experiments using their algorithms. The application field chosen for the experiments was the configuration of a car, such as would occur during a potential purchase. The algorithms are lucidly explained and interested readers should be able to implement them.