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 reasoning to problems with nary 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 neigh-bourhood 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.
展开▼
