Neighbourhood SAC for Constraint Satisfaction Problems with Non-Binary Constraints

Neighbourhood singleton arc consistency (NSAC) is a type of singleton arc consistency (SAC) in which the subproblem formed by variables adjacent to a variable with a singleton domain is made arc consistent. In this paper we consider how to apply this form of consistency reasoningto problems with n-ary constraints including global constraints. The chief problem encountered is that of neighbouring variables contained in a constraint that also includes non-neighbouring variables. In this case, a strict extension of NSAC involves projection of such constraints onto the neighbourhood variables, but for many global constraints this may be difficult to do in practice. Here, we consider a simple variant called restricted neighbourhood SAC, that avoids this problem. We compare the two approaches on random and structured problems and show that in all cases the restricted form of k-NSAC is nearly as effective as the unrestricted form.