allDifferent

alldifferent is a global constraint used in constraint programming and constraint satisfaction problems to enforce that a given set of variables take pairwise distinct values. Formally, for variables X1, X2, ..., Xn with finite domains D1, D2, ..., Dn, the constraint requires Xi ≠ Xj for all i ≠ j.

The primary purpose of the alldifferent constraint is to prune the search space by removing values that cannot participate in any feasible assignment. In practice, solvers employ specialized propagation algorithms that go beyond simple pairwise inequality, often achieving generalized arc consistency. The classic exact propagator, based on Régin’s algorithm, models the problem as a bipartite graph with one side representing variables and the other representing possible values. A maximum matching encodes a feasible assignment of distinct values. Pruning rules remove values that do not appear in any maximum matching, and further reductions rely on Hall’s condition to maintain consistency across the whole set of variables.

Computationally, the propagation is polynomial-time, with typical implementations using maximum matching techniques. While the cost can be higher than applying pairwise inequalities, the stronger pruning often yields substantial savings in search. Many constraint programming systems implement alldifferent as a dedicated global constraint, sometimes with variants that incorporate symmetry breaking, domain-specific heuristics, or combined constraints (for example, alldifferent with allowed values or with additional linear constraints).

Applications of alldifferent appear in scheduling, timetabling, Sudoku and Latin squares, resource allocation, and other combinatorial problems where distinct assignments are required. It is a foundational tool in modern constraint solvers and a standard building block for more complex models.