PyCSP³

Constraint Precedence

The constraint Precedence ensures that if a variable $x$ of a specified list of variables is assigned the $i + 1 t h$ value of a specified list $V$ of values, then another variable that precedes $x$ in the list of variables, is assigned the $i t h$ value of $V$ . In general, this constraint is useful for breaking value symmetries.

Below, we illustrate two representative use cases of the constraint Precedence.

Case 1: Precedence while Specifying Values

In PyCSP $^{3}$ , we must call the function Precedence() that allows us to pass the variables either in sequence (individually) or under the form of a list. A named parameter values allows to specify the values involved in the constraint.

It is also possible to use an optional named parameter covered: when True, each value of the specified list must be assigned by at least one variable in the scope of the constraint (by default, the value if False).

To see how this constraint works, we need first to import the library PyCSP $^{3}$ :

from pycsp3 import *

For our illustration, we introduce an array $x$ of 4 variables, each variable having {0,1, 2} as domain.

x = VarArray(size=4, dom={0, 1, 2})

We can display (the structure of) the array as well as the domain of the first variable.

print("Array of variable x: ", x)
print("Domain of any variable: ", x[0].dom)

Array of variable x:  [x[0], x[1], x[2], x[3]]
Domain of any variable:  0 1 2

First, we simply post a single constraint Precedence involving the values 0 and 1. This means that whenever 1 is assigned by a variable of $x$ , it is preceeded by 0.

satisfy(
     Precedence(x, values=[0,1])
);

By calling the function solve(), we can check that the problem (actually, the single constraint) is satisfiable (SAT). We can compute all solutions (supports) by setting the parameter sols to the constant ALL. We can also print the values assigned to the variables in the found solutions; we can call the function values() that collects the values assigned to a specified list of variables, while indicating the index of the solution with the parameter sol.

if solve(sols=ALL) is SAT:
     for i in range(n_solutions()):
        print(f"Solution {i+1}: {values(x, sol=i)}")

Solution 1: [0, 0, 0, 0]
Solution 2: [0, 0, 0, 1]
Solution 3: [0, 0, 0, 2]
Solution 4: [0, 0, 1, 2]
Solution 5: [0, 0, 2, 2]
Solution 6: [0, 0, 2, 0]
Solution 7: [0, 0, 1, 0]
Solution 8: [0, 0, 1, 1]
Solution 9: [0, 0, 2, 1]
Solution 10: [0, 1, 2, 1]
Solution 11: [0, 2, 2, 1]
Solution 12: [0, 2, 0, 1]
Solution 13: [0, 2, 1, 1]
Solution 14: [0, 1, 1, 1]
Solution 15: [0, 1, 0, 1]
Solution 16: [0, 1, 0, 0]
Solution 17: [0, 1, 0, 2]
Solution 18: [0, 1, 1, 2]
Solution 19: [0, 1, 2, 2]
Solution 20: [0, 1, 2, 0]
Solution 21: [0, 1, 1, 0]
Solution 22: [0, 2, 1, 0]
Solution 23: [0, 2, 0, 0]
Solution 24: [0, 2, 2, 0]
Solution 25: [0, 2, 2, 2]
Solution 26: [0, 2, 0, 2]
Solution 27: [0, 2, 1, 2]
Solution 28: [2, 0, 1, 2]
Solution 29: [2, 0, 0, 2]
Solution 30: [2, 0, 2, 2]
Solution 31: [2, 2, 2, 2]
Solution 32: [2, 2, 0, 2]
Solution 33: [2, 2, 0, 0]
Solution 34: [2, 2, 0, 1]
Solution 35: [2, 2, 2, 0]
Solution 36: [2, 0, 2, 0]
Solution 37: [2, 0, 2, 1]
Solution 38: [2, 0, 0, 1]
Solution 39: [2, 0, 1, 1]
Solution 40: [2, 0, 1, 0]
Solution 41: [2, 0, 0, 0]

Now, let us discard this constraint:

unpost()

Let us check that there are no more constraints:

print(posted())

[]

This time, let us post a constraint Precedence while indicating three values:

satisfy(
     Precedence(x, values=[0,1,2])
);

Let us display all solutions:

if solve(sols=ALL) is SAT:
     for i in range(n_solutions()):
        print(f"Solution {i+1}: {values(x, sol=i)}")

Solution 1: [0, 0, 0, 0]
Solution 2: [0, 0, 0, 1]
Solution 3: [0, 0, 1, 1]
Solution 4: [0, 0, 1, 0]
Solution 5: [0, 0, 1, 2]
Solution 6: [0, 1, 1, 2]
Solution 7: [0, 1, 1, 0]
Solution 8: [0, 1, 1, 1]
Solution 9: [0, 1, 0, 1]
Solution 10: [0, 1, 2, 1]
Solution 11: [0, 1, 2, 0]
Solution 12: [0, 1, 2, 2]
Solution 13: [0, 1, 0, 2]
Solution 14: [0, 1, 0, 0]

Case 2: Precedence without Specifying Values

Let us start by discarding the last posted constraint:

unpost()

Let us check that there are no more constraints:

print(posted())

[]

And let us post a constraint Precedence without indicating any values. This is equivalent to indicate the ordered list of values that can be collected over the domains of the variables involved in the constraint. Here, it is equivalent to [0,1,2].

satisfy(
     Precedence(x)
);

Let us display all solutions:

if solve(sols=ALL) is SAT:
     for i in range(n_solutions()):
        print(f"Solution {i+1}: {values(x, sol=i)}")

Solution 1: [0, 0, 0, 0]
Solution 2: [0, 0, 0, 1]
Solution 3: [0, 0, 1, 1]
Solution 4: [0, 0, 1, 0]
Solution 5: [0, 0, 1, 2]
Solution 6: [0, 1, 1, 2]
Solution 7: [0, 1, 1, 0]
Solution 8: [0, 1, 1, 1]
Solution 9: [0, 1, 0, 1]
Solution 10: [0, 1, 2, 1]
Solution 11: [0, 1, 2, 0]
Solution 12: [0, 1, 2, 2]
Solution 13: [0, 1, 0, 2]
Solution 14: [0, 1, 0, 0]

We can observe thet this way of posting the constraint Precedence is indeed equivalent to the last previsouly post operation (for Case 1).

Since XCSP $^{3}$ Specifications 3.1, Precedence belongs to XCSP $^{3}$ -core.

Constraint Precedence

Case 1: Precedence while Specifying Values

Case 2: Precedence without Specifying Values

Related Models