Constraint AllDifferent
The constraint AllDifferent ensures that the elements (most the time, variables) from a specified list take different values.
Below, we give several illustrations corresponding to representative use cases of the constraint AllDifferent.
Case 1: AllDifferent on Variables
The first, and usual, case is when a list of variables is specified.
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 one with {0,1,2,3} as domain.
x = VarArray(size=4, dom=range(4))
We can display (the structure of) the array as well as the domains of the four variables.
print("Array of variable x: ",x)
for i in range(4):
print(f"Domain of {x[i]}: {x[i].dom}")
Array of variable x: [x[0], x[1], x[2], x[3]]
Domain of x[0]: 0..3
Domain of x[1]: 0..3
Domain of x[2]: 0..3
Domain of x[3]: 0..3
We simply post a single constraint AllDifferent on the variables of $x$:
satisfy(
AllDifferent(x)
);
By calling the function solve(), we can check that the problem (actually, the single constraint) is satisfiable (SAT). We can also print the values assigned to the variables in the found solution; we can call the function values() that collects the values assigned (in the last found solution) to a specified list of variables.
if solve() is SAT:
print("Solution: ", values(x))
Solution: [0, 1, 2, 3]
If ever we want to count the number of solutions, we can use the named parameter sols. Because here the number of variables (4) is equal to the number of values (4), the number of solutions is exactly the number of permutations (4!=24). Note how the named parameter sol of values() is used to indicate the index of a solution.
if solve(sols=ALL) is SAT:
for i in range(n_solutions()):
print(f"Solution {i+1}: {values(x, sol=i)}")
Solution 1: [0, 1, 2, 3]
Solution 2: [0, 1, 3, 2]
Solution 3: [0, 3, 1, 2]
Solution 4: [0, 3, 2, 1]
Solution 5: [0, 2, 1, 3]
Solution 6: [0, 2, 3, 1]
Solution 7: [1, 2, 3, 0]
Solution 8: [1, 2, 0, 3]
Solution 9: [3, 2, 1, 0]
Solution 10: [3, 2, 0, 1]
Solution 11: [3, 1, 0, 2]
Solution 12: [2, 1, 0, 3]
Solution 13: [2, 3, 0, 1]
Solution 14: [1, 3, 0, 2]
Solution 15: [1, 3, 2, 0]
Solution 16: [1, 0, 2, 3]
Solution 17: [1, 0, 3, 2]
Solution 18: [2, 0, 3, 1]
Solution 19: [2, 1, 3, 0]
Solution 20: [3, 1, 2, 0]
Solution 21: [2, 3, 1, 0]
Solution 22: [2, 0, 1, 3]
Solution 23: [3, 0, 1, 2]
Solution 24: [3, 0, 2, 1]
Although this is not the most efficient way of doing that, an alternative is to iteratively add a constraint that forbids the last found solution and to call solve(). This way, after each solution, a new instance is generated and the solver is loaded (in the future, we plan to be able to let the solver alive). Hence, we can enumerate all solutions (supports) of the constraint as follows:
cnt = 0
while solve(solver=CHOCO) is SAT:
cnt += 1
print(f"Solution {cnt}: {values(x)}")
satisfy(
x != values(x)
)
Solution 1: [2, 1, 0, 3]
Solution 2: [3, 1, 0, 2]
Solution 3: [1, 3, 0, 2]
Solution 4: [1, 2, 0, 3]
Solution 5: [2, 3, 0, 1]
Solution 6: [3, 2, 0, 1]
Solution 7: [0, 3, 2, 1]
Solution 8: [0, 2, 3, 1]
Solution 9: [0, 2, 1, 3]
Solution 10: [0, 3, 1, 2]
Solution 11: [0, 1, 3, 2]
Solution 12: [0, 1, 2, 3]
Solution 13: [3, 1, 2, 0]
Solution 14: [2, 1, 3, 0]
Solution 15: [3, 2, 1, 0]
Solution 16: [2, 3, 1, 0]
Solution 17: [1, 2, 3, 0]
Solution 18: [1, 3, 2, 0]
Solution 19: [2, 0, 1, 3]
Solution 20: [3, 0, 1, 2]
Solution 21: [1, 0, 2, 3]
Solution 22: [1, 0, 3, 2]
Solution 23: [3, 0, 2, 1]
Solution 24: [2, 0, 3, 1]
Suppose now that we arbitrarily remove the value 3 from the domain of the two last variables. We can check that no more solution exists because the result is now UNSAT; one can observe in the previous enumeration of solutions that it is not possible to have 3 assigned to both $x[2]$ and $x[3]$.
satisfy(
x[2] != 3,
x[3] != 3
)
print("Result: ", solve())
Result: UNSAT
Case 2: AllDifferent on Expressions
The second case is when a list of expressions (not single variables) is specified.
First of all, we need to remove everything that has been introduced so far by calling the function clear().
clear() # to clear previously posted variables and constraints
As earlier, we introduce an array $x$ of 4 variables, each one with ${0,1,2,3}$ as domain.
x = VarArray(size=4, dom=range(4))
Then, we post a single constraint AllDifferent on some expressions linking variables of $x$.
satisfy(
AllDifferent(abs(x[1]-x[0]), abs(x[2]-x[1]), abs(x[3]-x[2]), abs(x[0]-x[3]))
);
We can display the internal representation of the constraint that we have just posted; note that dist(a,b) is equivalent to abs(a-b).
print(posted())
allDifferent(list:[dist(x[1],x[0]), dist(x[2],x[1]), dist(x[3],x[2]), dist(x[0],x[3])])
We can run the solver.
if solve() is SAT:
print("Solution: ", values(x))
Solution: [0, 0, 1, 3]
On can check that the four expressions are different.
Case 3: AllDifferent with Exceptions
A variant, sometimes called AllDifferentExcept in the literature, enforces variables to take distinct values, except those that are assigned to some specified values (often, the single value 0). We use a named parameter called excepting for indicating the value(s) that must be ignored.
To start, we remove the last posted constraint by calling the function unpost().
unpost()
We control that there are no more constraints.
print(posted())
[]
Then, we post a single constraint AllDifferent on the variables of $x$, while indicating that the value 0 must be ignored.
satisfy(
AllDifferent(x, excepting=0)
);
When solutions are enumerated, one can see that the special value 0 is ignored. Here, we enumerate the 20 first solutions.
if solve(sols=20) is SAT:
for i in range(20):
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, 0, 3]
Solution 5: [0, 0, 1, 3]
Solution 6: [0, 0, 2, 3]
Solution 7: [0, 0, 2, 0]
Solution 8: [0, 0, 1, 0]
Solution 9: [0, 0, 3, 0]
Solution 10: [0, 0, 3, 1]
Solution 11: [0, 0, 2, 1]
Solution 12: [0, 0, 1, 2]
Solution 13: [0, 0, 3, 2]
Solution 14: [0, 1, 3, 2]
Solution 15: [0, 1, 0, 2]
Solution 16: [0, 3, 0, 2]
Solution 17: [0, 3, 1, 2]
Solution 18: [0, 3, 1, 0]
Solution 19: [0, 3, 0, 0]
Solution 20: [0, 3, 2, 0]