Abstract
Backtracking search is frequently applied to solve
a constraint-based search problem
but it often suffers from exponential growth
of computing time.
We present an alternative to backtracking search:
local search based on conflict minimization.
We have applied this general search framework
to study a benchmark constraint-based search problem,
the n-queens problem.
An efficient local search algorithm
for the n-queens problem was implemented.
This algorithm,
running in linear time,
does not backtrack at all.
It is capable of finding a solution for
extremely large size n-queens problems.
For example, on a workstation computer,
it can find a solution for 3,000,000 queens
in less than 55 seconds.