Constraint Satisfaction Problems

A constraint is simply a (logical) relation among several variables, each of which is allowed to take a value
in a given domain. A constraint therefore restricts the possible values that variables can take. It thus
represents some partial information about the variables of interest. For instance, in the cryptarithmetic
puzzle, SEND + MORE = MONEY , the variables are letters of the English alphabet. Each variable is
allowed to take integer values from 0 through 9, and the constraints are imposed by the laws of base-10
arithmetic.

Some properties of constraints are worth noting: Constraints may specify partial information, i.e., constraint
need not uniquely specify the values of its variables. Constraints are declarative, i.e., they specify what
relationship must hold without specifying how such a relationship is to be enforced. The effect of constraints
are additive and independent of the order in which the constraints are enforced. Constraints are rarely
independent, i.e., each constraint involves several variable, and each variable is subject to several constraints.

Course Book Reference for this submodule

Part II Problem-solving

Chapter 6 Constraint Satisfaction Problems ... 180

Beginning with the pioneering work of Mackworth, Waltz, and others, in the 1970s, constraint satisfaction
problems have been studied extensively in AI. They have found applications in diverse problem domains
including temporal reasoning (pioneered by James Allen), scheduling, planning, natural language processing,
computational biology, among others. This has led to the development of a variety of languages and systems
for specification and solution of CSP.

Online Lectures on CSP

Constraint Satisfaction Part I

Constraint Satisfaction Part II

Constraint Satisfaction Part I (UC Berkeley)

Constraint Satisfaction Part II (UC Berkeley) [start at 5:36]

Interview and guest lecture with AI Researcher in CSP - (will be posted by end of April)

Additional Resources

Chapters 1 and 2 from Foundations of Constraint Satisfaction, by Edward Tsang.
Temporal Reasoning by James Allen