Efficient local search with conflict minimization: a case study of the n-queens problem
- 1 January 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 6 (5) , 661-668
- https://doi.org/10.1109/69.317698
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 with 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. It is capable of finding a solution for extremely large size n-queens problems. For example, on a workstation it can find a solution for 3000000 queens in less than 55 sKeywords
This publication has 16 references indexed in Scilit:
- Efficient local search for very large-scale satisfiability problemsACM SIGART Bulletin, 1992
- On a general framework for large-scale constraint-based optimizationACM SIGART Bulletin, 1991
- Explicit solutions to the N -queens problem for all NACM SIGART Bulletin, 1991
- An almost perfect heuristic for the N nonattacking queens problemInformation Processing Letters, 1990
- Divide and conquer under global constraints: A solution to the N-queens problemJournal of Parallel and Distributed Computing, 1989
- Efficient search techniques—An empirical study of the N-Queens ProblemIBM Journal of Research and Development, 1987
- A note on the queen's problemInformation Processing Letters, 1986
- Increasing tree search efficiency for constraint satisfaction problemsArtificial Intelligence, 1980
- Backtrack programming techniquesCommunications of the ACM, 1975
- Constructions for the Solution of the m Queens ProblemMathematics Magazine, 1969