Physical Sciences and Mathematics Commons^™

A new language, called constraint CNF, is proposed. It integrates propositional logic with constraints stemming from constraint programming (CP). A family of algorithms is designed to solve problems expressed in constraint CNF. These algorithms build on techniques from both propositional satisfiability (SAT) and CP. The result is a uniform language and an algorithmic framework, which allow us to gain a deeper understanding of the relation between the solving techniques used in SAT and in CP and apply them together.