Solving N-ary constraint labeling problems using incremental subnetwork consistency

Abstract

The authors present an algorithm for finding all solutions of n-ary constraint labeling problems while building constraint networks. The key principle of the algorithm is to alternate the instantiation of a newly chosen variable, and making domain values of already instantiated (non-future) variables consistent among them, until all variables are considered. The algorithm chooses variables for domain instantiation one at a time; assigns all viable domain values to it, instead of a single one; adds the variable to the constraint network, resulting in a subnetwork whose order is greater than the previous one; and achieves consistencies within subnetworks of the nonfuture variables in an incremental manner. In this algorithm, any inconsistent domain values are eliminated once and for all. The proposed constraint labeling algorithm does not exhibit the stacking-unstacking problem which most of hybrid algorithms have. In addition, this algorithm is more efficient than E. C. Freuder's (1978) constraint synthesis algorithm because the latter attempts to achieve strong k-consistencies over n variables.