3,000,000 Queens in less than one minute
- 1 February 1991
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGART Bulletin
- Vol. 2 (2) , 22-24
- https://doi.org/10.1145/122319.122325
Abstract
The n - queens problem is a classical combinatorial search problem. In this paper we give a linear time algorithm for this problem. The algorithm is an extension of one of our previous local search algorithms [3, 4, 6]. On an IBM RS 6000 computer, this algorithm is capable of solving problems with 3,000,000 queens in approximately 55 seconds.Keywords
This publication has 4 references indexed in Scilit:
- A polynomial time algorithm for the N-Queens problemACM SIGART Bulletin, 1990
- Efficient search techniques—An empirical study of the N-Queens ProblemIBM Journal of Research and Development, 1987
- The average complexity of depth-first search with backtracking and cutoffIBM Journal of Research and Development, 1986
- Increasing tree search efficiency for constraint satisfaction problemsArtificial Intelligence, 1980