A Fast and Simple Algorithm for Bounds Consistence of the Alldifferent Constraint. A. López-Ortiz, Claude-Guy Quimper, John Tromp and Peter van Beek. In Proceedings of 18^th International Joint Conference on Artificial Intelligence (IJCAI), pp. 245-250, 2003 [Postscript file]

Abstract.
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. In the general case the algorithm has the same worst case behavior as the previous best algorithms 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.