Stronger integration of circuit and alldifferent propagators for the Hamiltonian Cycle Problem

Global constraints are one of the features that make Constraint Programming an effective solution scheme. The first global constraint, named alldifferent, is also one of the most used. In order to solve in Constraint Programming routing problems, such as the Hamiltonian Circuit Problem, the Travelling Salesperson Problem and many of their variants, an effective solution is to use a constraint model containing alldifferent and the circuit constraint, necessary to avoid sub-circuits. In this paper, we propose a combination of alldifferent and circuit that reuses the data structures of the alldifferent constraint to perform further propagation for the circuit constraint. The new combination introduces negligible overhead, and experimental results show that it can be effective when solving the Hamiltonian Circuit Problem.