Variables, Domains, and Constraints

Introduces the three core components of a constraint satisfaction problem (CSP): decision variables, their domains, and the constraints that restrict allowed assignments. Students learn to identify variables and domains for a problem, check whether an assignment satisfies a set of constraints, and model small problems as complete CSPs.

Step 1 of 157%

Tutorial

Decision Variables and Domains

In constraint programming, a decision variable is an unknown quantity whose value we need to determine. Each decision variable $x$ is associated with a domain $D(x)$ -- the set of values that $x$ is allowed to take.

For example, suppose we must choose a starting hour for a meeting on a $24$ -hour clock, restricted to working hours between $9$ and $17$ . The decision variable is the start time $s$ , and its domain is

D(s) = \{9, 10, 11, 12, 13, 14, 15, 16, 17\}.

Domains come in several flavors:

Boolean: $D(x) = \{0, 1\}$ or $\{\text{true}, \text{false}\}$ .
Discrete finite: $D(x) = \{\text{red}, \text{green}, \text{blue}\}$ or $\{1, 2, \ldots, 9\}$ .
Integer interval: $D(x) = [1..100]$ , meaning every integer from $1$ to $100$ .
Continuous interval: $D(x) = [0.0, 1.0]$ .

A choice of a value from $D(x)$ for the variable $x$ is called an assignment, written $x = v$ . An assignment of values to every variable in the problem is called a complete assignment.