<p>The alldifferent constraint is one of the most essential global constraints that has been used to model many classic Constraint Satisfaction Problems (CSPs). To tackle this constraint, previous work generally focuses on proposing filtering algorithms to reduce the value domain of variables, thereby pruning the backtracking search. However, due to the inherent complexity of alldifferent constraints, it remains challenging to solve CSPs containing large-scale alldifferent constraints for the existing search-based solvers. In this paper, we propose an efficient local search algorithm, called AllDiff-LS. We first represent the set of alldifferent constraints as graphs and simplify the graphs by two polynomial-time reduction rules. Afterward, we propose a new two-step strategy for selecting moves, as well as the carefully crafted tabu and restart strategies, to enable the algorithm to explore the search space more efficiently. Experiments on a representative set of benchmarks show that AllDiff-LS successfully solves more instances compared with state-of-the-art complete and heuristic methods, especially on large-scale instances, with much less running time.</p>