Constraints

$X_1 < X_2$

Such a constraint will take two variables as argument and makes sure that the former one takes a value less than the latter one in any solution.

$(1,2)$ and $(2,5)$ satisfy the constraint,

$(2,2)$ and $(5,3)$ do not.

We will first create a class to declare the behaviour of this constraint:

class LessThan:
    def __init__(self, v1, v2):
        self.v1 = v1
        self.v2 = v2

We can impose that $X_1$ is strictly less than $X_2$:

variables = {"x1": {1, 2, 3},
             "x2": {1, 2, 3}}
c1 = LessThan("x1", "x2") # means that x1 < x2 should hold

What can such a constraint do?

In CP, we remove

The basic behaviour of a constraint is to remove from the variable domain those values that cannot be extended to any solution

(according to its own contract)

We will create an empty function called filter as follow:

def filter(self,variables):
	pass

The 2 rules of $X_1 < X_2$

1. removing from $X_1$ values greater or equal to the largest value in $X_2$,

2. removing from $X_2$ values smaller or equal to the smallest value in $X_1$.

Otherwise, in both cases, we could break the contract established between the 2 variables.

$X_1 = \{1,2,3,4\}$, $X_2 = \{1,2,3,4\}$ and $X_1 < X_2$

Then

  • 4 is removed from $X_1$
  • 1 is removed from $X_2$

In other words:

  • $max(X_2)$ and larger are removed from $X_1$
  • $min(X_1)$ and smaller are removed from $X_2$

Deal with dead ends

We can tell that the constraint should return :

  • True : if some values were filtered
  • False : if a domain becomes empty
  • None : if nothing was filtered

LessThan filtering algorithm

class LessThan:
    def __init__(self, v1, v2):
        self.v1 = v1
        self.v2 = v2

    def filter(self, variables):
        """
        Filter the domain of the variables declared in 'vars'.
        The method directly modifies the entries of 'vars'.
        It returns True if some values were filtered,
        False if a domain becomes empty,
        None otherwise.
        """
        pass

>>🥛<<

LessThan filtering algorithm

def filter(self, variables):
    cd1 = variables[self.v1] # get current domain of "x1"
    cd2 = variables[self.v2] # get current domain of "x2"
    # filtering according to the 1st rule
    nd1 = {v for v in cd1 if v < max(cd2)}
    if len(nd1) == 0: # "x1" becomes empty...
        return False
    # filtering according to the 2nd rule
    nd2 = {v for v in cd2 if v > min(cd1)}
    if len(nd2) == 0: # "x2" becomes empty...
        return False
    variables[self.v1] = nd1 # update the domain of "x1"
    variables[self.v2] = nd2 # update the domain of "x2"
    modif = cd1 > nd1 or cd2 > nd2 # reduction of a domain
    return modif or None

Does that work?

# declare a CSP
variables = {"x1": {1, 2, 3},
             "x2": {1, 2, 3}}
c1 = LessThan("x1", "x2")
# call the filtering algorithm
modif = c1.filter(variables)
# check everything works fine
assert variables["x1"] == {1, 2}
assert variables["x2"] == {2, 3}
assert modif == True

Yes, it does !