(PDF) Alejandro Lopez-Ortiz, Claude-Guy Quimper, John Tromp, and Peter van Beek. A fast and simple algorithm for bounds consistency of the alldifferent constraint. Proceedings of the 18th International Joint Conference on Artificial Intelligence, Acapulco, Mexico, 245-250, August, 2003. A longer technical report version is available.
In constraint programming one models a problem by stating constraints on acceptable solutions. The constraint model is then usually solved by interleaving backtracking search and constraint propagation. Previous studies have demonstrated that designing special purpose constraint propagators for commonly occurring constraints can significantly improve the efficiency of a constraint programming approach. In this paper we present a fast, simple algorithm for bounds consistency propagation of the alldifferent constraint. The algorithm has the same worst case behavior as the previous best algorithm but is much faster in practice. Using a variety of benchmark and random problems, we show that our algorithm outperforms existing bounds consistency algorithms and also outperforms---on problems with an easily identifiable property---state-of-the-art commercial implementations of propagators for stronger forms of local consistency.
An implementation of the algorithm for bounds consistency propagation of the alldifferent constraint presented in the paper: README, alldifferent.tar.gz
Also included are some example benchmark and random problems that use the alldifferent constraint.
Note: All of the code relies on the ILOG Solver Library.