Exploiting Interchangeabilities in Constraint-Satisfaction Problems

Abstract

Constraint satisfaction - a method for representing and solving many AI problems in a very elegant manner - is a well-studied research area of recent years. Freuder observed that some constraint satisfaction problems are fashioned so that certain domain values of constraint variables are interchangeable. The use of such knowledge can increase search efficiency drastically by reducing the problem. In this paper we carry on these considerations and give a formal foundation of interchangeabilities by the notion of domain partitions induced by equivalence relations. We show how these domain partitions can be used in a very accurate manner by the majority of existing constraint propagation algorithms and introduce a novel backtrack procedure exploiting such interchangeabilities of domain values. Both theoretical analysis and experiments indicate that our proposed approach is an improvement of Freuder's use of neighborhood interchangeability and has very good behavior for certain problem types.