Intermediate consistencies by delaying expensive propagators

What makes a good consistency? Depending on the constraint, it may be a good pruning power or a low computational cost. By weakening arc-consistency, we propose to dene new automatically generated solvers which form a sequence of consistencies weaker than arc-consistency. The method presented in this pa-per exploits a form of regularity in the cloud of con-straint solutions: the density of solution orthogonal to a projection. This approach is illustrated on the sparse constraints to be a n-letters english word and cross-word CSPs, where interesting speed-ups are obtained