An Efficient Cross Product Representation of the Constraint Satisfaction Problem Search Space

Constraint satisfaction problems involve finding values for variables subject to constraints on which combinations of values are permitted. They arise in a wide variety of domains, ranging from scene analysis to temporal reasoning. We present a new representation for partial solutions as cross products of sets of values. This representation can be used to improve the performance of standard algorithms, especially when seeking all solutions or discovering that none exist.