In combinatorial problems it is often worthwhile simplifying the problem, using operations such as consistency, before embarking on an exhaustive search for solutions. Neighbourhood substitution is such a simplification operation. Whenever a value x for a variable is such that it can be replaced in all constraints by another value y, then x is eliminated. This paper shows that neighbourhood substitutions are important whether the aim is to find one or all solutions. It is proved that the result of a convergent sequence of neighbourhood substitutions is invariant module isomorphism. An efficient algorithm is given to find such a sequence. It is also shown that to combine consistency (of any order) and neighbourhood substitution, we only need to establish consistency once.
