1. Element1D Constraint

Given an array T of integers and the variables y and z, the Element1D constraint enforces that z takes the value at index y of T: the relation T[y]=z must hold (where indexing starts from 0).

Assuming T=[1,3,5,7,3], the constraint holds for

y = 1, z = 3
y = 3, z = 7

but is violated for

y = 0, z = 2
y = 3, z = 3

Implement a bound consistent propagator Element1D.java by following the ideas (also in the slides) for Element2D, which however do not lead to domain consistency for both variables. Check that your implementation passes the tests Element1DTest.java.

1. Element1D Domain consistent

Now that you have implemented a bound consistent propagator for the Element1D constraint, you can implement another one for the same constraint, reaching domain consistency.

Within Element1DDomainConsistent.java, implement the propagator that achieves domain consistency for both variables.

One way to implement the domain-consistent version is to check if the constraint holds for every value within the domain of y and z. To iterate over their domains, you can use your efficient IntVar.fillArray that you implemented previously:

int size = y.fillArray(values);
for (int i = 0 ; i < size ; i++) {
    int valueOfY = values[i];
    // check if valueOfY (one element from the domain of y) is valid. Remove it otherwise
}

Keep in mind that values should be a container array stored as an instance variable from Element1DDomainConsistent and reused many times. It is important for efficiency to avoid creating objects on the heap at each execution of a propagator. Never forget that a propagate() method of Constraint may be called thousands of times per second.

Check that your implementation passes the tests Element1DDCTest.java.

3. Element1DVar Constraint with an Array of Variables

Implement a propagator Element1DVar.java. This constraint is more general than Element1D above, since T is here an array of variables.

The filtering algorithm is nontrivial, at least if you want to do it efficiently. Two directions of implementation are:

• The hybrid domain-bound consistent propagator achieves bounds consistency for z and all the T[i] but domain consistency for y.
• The domain-consistent propagator achieves domain consistency for y, z, and all the T[i].

Check that your implementation passes the tests Element1DVarTest.java. Those tests do not check that your propagator achieves domain consistency for all the variables, so you have to write additional tests in order to help convince yourself that it does so, if you take that direction.

4. The Stable Matching Problem

Complete the partial model StableMatching.java. It makes use of the Element1DVar constraint you have just implemented and is also a good example of the manipulation of logical and reified constraints. Ensure that your implementation discovers all 6 solutions to the provided instance. Check that your implementation passes the tests StableMatchingTest.java.

hint1: Some constraints will need to be modeled using Element1DVar when one of the argument is a constant instead of a variable. To transform an int z into a variable, you can create an IntVar with z as its unique value, by using makeIntVar(cp, z, z):

IntVar[] T = ...;
IntVar y = ...;
int z = ...; // not an IntVar
// does not work
cp.post(new Element1DVar(T, y, z));
// this works!
cp.post(new Element1DVar(T, y, makeIntVar(cp, z, z)));

hint2: Some constraints are modeled using implication. A static method implies is provided to you within StableMatching.java.