LOCAL SEARCH WITH CONFLICT MINIMIZATION - A CASE-STUDY OF THE N-QUEENS PROBLEM

Backtracking search is frequently applied to solve a constraint-based search problem, but it often suffers form exponential growth of comput ing time. We present an alternative to backtracking search: local sear ch with conflict minimization. We have applied this general search fra mework to study a benchmark constraint-based search problem, the n-que ens problem. An efficient local search algorithm for the n-queens prob lem ws implemented. This algorithm, running in linear time, does not b acktrack. It is capable of finding a solution for extremely large size n-queens problems. For example, on a workstation computer, it can fin d a solution for 3 000 000 queens in less than 55 s.