Если Вы найдете статью полезной и интересной - не сочтите за труд, переведите материал или хотя бы часть его и отправьте на адрес algolist@mail.ru. Задать вопросы или просто написать письмо можно также на странице контактов.

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.