The following section will briefly outline how the dependency information is gathered and recorded. The main goal of this section is to set up the data structures that will be used by the algorithms in the following sections. As shown in the discussion about AC-4 above, it is advantageous to store, for each possible value of each variable, those values in other variables that will satisfy constraints. We also find it advantageous to store, for each value of each variable, values of other variables that conflict with constraints.
Figure 15, a copy of Figure 6B, shows a simple constraint problem.
Data structures can be constructed such that the arrays Needed and
Fails
produce
the following results:
where A is the name of a variable, X is a value from its domain, and
represent variable-value pairs that will satisfy (for Needed)
or conflict with (for Fails) constraint C given the assignment X to A.
The constraint involved, C, must be recorded for Needed because for
each constraint, the list of Neededs will need to be consulted
separately. If any of the constraints has a list of Neededs that are
all failed, then the value assignment is invalid. For Fails, the
constraint information is not needed, since the <A,X> value assignment will
automatically fail all of the B variable assignments listed.
For example,
It is also convenient to have a simple array noting which constraints apply to which variables:
A simple algorithm that performs these tasks would be:
1 PROCEDURE SET-UP-CONSTRAINTS2 FOR each Constraint
3 ;; determine which variables, A and B are involved
4 Constraints[A] <-- Constraints[A] + Constraint
5 Constraints[B] <-- Constraints[B] + Constraint
6 FOR each value, X, in A's domain
7 FOR each value, Y, in B's domain
8 IF ¯ (X,Y) SAT Constraint THEN
9 Needed
Needed
10 Needed
Needed
11 ELSE
12
13
If the maximum size of any domain is a and the number of
constraints, or arcs, is e, then this algorithm has
time complexity of O(e
).
