Steven Minton, Mark D. Johnston, Andrew B. Philips, and Philip Laird
One of the most promising general approaches for solving combinatorial search problems is to generate an initial, suboptimal solution and then to apply local repair heuristics. Techniques based on this approach have met with empirical success on many combinatorial problems, including the traveling salesman and graph partitioning problems. Such techniques also have a long tradition in AI, most notably in problemsolving systems that operate by debugging initial solutions. In this paper, we describe how this idea can be extended to constraint satisfaction problems (CSPs) in a natural manner.