Although satisfiability (SAT) and constraint programming (CP) problems can intuitively be seen as somewhat close to each other, the truth is that both types of problems are approached in rather different ways by completely different scientific communities. SAT is a very well-known problem for the computer science community, and “constraint satisfaction is a simple but powerful idea” [1], which generalizes many of the concepts present in SAT.

The paper is arranged in well-differentiated sections, each divided into self-contained subsections that discuss different topics for both SAT and CP. In other words, the paper is not arranged as a joint discussion of the differences and similarities of similar techniques for both fields, but as a separate collection of algorithms. Although consideration of the similarities and differences between SAT and CP appear throughout the paper, it is not until the end that the authors intentionally meditate on this issue.

After sketchily defining both types of problems and dealing with various representation issues, the paper immediately starts with the description of various algorithms in section 4. Up to this point, almost every reader should have no problem understanding the main ideas. Sections 5 and 6 are devoted to more technical questions, and some descriptions become more obscure and difficult to understand (for example, supports are repeatedly mentioned on pages 26 and 27, but the term is never defined). Section 7 on backtracking, on the other hand, is very clear; even those familiar with the subject are advised to read it. The paper ends with other considerations regarding optimization and parallel/distributed architectures. All in all, this paper is a major step toward unifying our understanding of both SAT and CP.