### 4.2.1 Constraints

In many domains, not all possible assignments of values to variables
are permissible. A **hard constraint**, or simply constraint, specifies legal combinations of
assignments of values to the variables.

A **scope** or **scheme** is a set of variables. A
**tuple** on scope *S* is an assignment of a value to each variable in *S*.
A **constraint** *c* on a scope *S* is a set
of tuples on *S*. A constraint is said to **involve** each of
the variables in its scope.

If *S'* is a set of variables such that *S⊆S'*, and *t* is a
tuple on *S'*,
constraint *c* is said to **satisfy** *t* if *t*, restricted to
*S*, is in *c*.

Constraints can be defined using the terminology of
relational databases. The
main difference between constraints and database relations is that a constraint specifies legal values, whereas a
database relation specifies what happens to be true in some situation. Constraints are
also often defined **intensionally**, in terms of predicates (Boolean functions), to
recognize legal assignments rather than **extensionally** by
representing each assignment explicitly in a table. Extensional definitions can be
implemented either by representing the legal assignments or by representing the illegal assignments.

**Example 4.7:**Consider a constraint on the possible dates for three activities. Let

*A*,

*B*, and

*C*be variables that represent the date of each activity. Suppose the domain of each variable is

*{1,2,3,4}*.

The constraint could be written as a table that gives the legal combinations:

A | B | C |

2 | 2 | 4 |

1 | 1 | 4 |

1 | 2 | 3 |

1 | 2 | 4 |

which has scope *{A,B,C}*. Each row is a tuple that specifies a
legal assignment of a value to each variable in the scope of the constraint. The first tuple is

{A=2,B=2,C=4}.

This tuple, which assigns *A* the value of 2, *B* the value of 2, and *C*
the value of 4, specifies one of the four legal assignments of the
variables.

This constraint satisfies the tuple *{A=1,B=2,C=3,D=3,E=1}*, because that
tuple assigns legal values to the variables in the scope.

This constraint could also be described intensionally by using a predicate - a logical formula - to specify the legal assignments. The preceding constraint could be specified by

(A ≤ B) ∧(B<3) ∧(B<C) ∧¬(A=B ∧C=3),

where *∧* means *and*, and *¬* means *not*.
This formula says that *A* is on the same date or before *B*, and *B* is before
*3*, and *B* is before *C*, and it cannot be that *A* and *B* are on the
same date and *C* is on day 3.

A **unary constraint** is a constraint on a single
variable (e.g., *X≠4*). A **binary constraint** is a constraint over a
pair of variables (e.g., *X≠Y*). In general, a *k*-ary constraint
has a scope of size *k*.

A possible world *w* **satisfies** a set of constraints if, for
every constraint, the values assigned in *w* to the variables
in the scope of the constraint satisfy the constraint. In this case, we
say that the possible world is a **model** of the
constraints. That is, a **model** is a possible world that satisfies all
of the constraints.

**Example 4.8:**Suppose the delivery robot must carry out a number of delivery activities,

*a*,

*b*,

*c*,

*d*, and

*e*. Suppose that each activity happens at any of times

*1*,

*2*,

*3*, or

*4*. Let

*A*be the variable representing the time that activity

*a*will occur, and similarly for the other activities. The variable domains, which represent possible times for each of the deliveries, are

*dom(A)={1,2,3,4},dom(B)={1,2,3,4},dom(C)={1,2,3,4},*

*dom(D)={1,2,3,4},dom(E)={1,2,3,4}.*

Suppose the following constraints must be satisfied:

{(B≠3), (C≠2), (A≠B), ( B≠C), (C<D), (A=D),

(E<A), (E<B), (E<C), (E<D), ( B≠D)}

The aim is to find a model, an assignment of a value to each variable, such that all the constraints are satisfied.

**Example 4.9:**Consider the constraints for the two representations of crossword puzzles of Example 4.4.

- For the case in which the domains are words, the constraint is that the letters where a pair of words intersect must be the same.
- For the representation in which the domains are the letters, the constraint is that contiguous sequences of letters must form legal words.

**Example 4.10:**In Example 4.6, consider some typical constraints. It may be that certain activities have to be on different days or that other activities have to be in the same town on the same day. There may also be constraints that some activities must occur before other activities, or that there must be a certain number of days between two activities, or that there cannot be three activities on three consecutive days.