The Symmetric Alldiff Constraint

Abstract

The symmetric alldiff constraint is a particular case of the all diff constraint, a case in which variables and values are defined from the same set 5. That is, every variable represents an element c of S and its values represent the elements of S that are compatible with c. This constraint requires that all the values taken by the variables are different (similar to the classical all diff constraint) and that if the variable representing the element i is assigned to the value representing the element j, then the variable representing the element j is assigned to the value representing the element?. This constraint is present in many real-world problems, such sports scheduling where it expresses matches between teams. In this paper, we show how to compute the arc consistency of this constraint in O(n,m) (m = Σi|D(i)|), where n is the number of involved variables and D(i) the domain of the variable i. We also propose a filtering algorithm of less complexity (O(m)).