Abstract
This report addresses the problem of improving algorithms for solving consistent labeling (also called constraint -satisfaction) problems. The concept of compatibility between variables in such problems is introduced. How to obtain compatibilities analytically and empirically is discussed, and various compatibility-based heuristics (as well as some useful but less effective non compatibility-based heuristics) are developed to improve a version of the Waltz algorithm, which was found best of a set of consistent-labeling problem algorithms, tested by Haralick [5]. Empirical results with these heuristics are very encouraging, with over an order of magnitude improvement in performance with respect to the basic algorithm on a set of randomly generated consistent- labeling problems.