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. On an IBM RS 6000 computer, this algorithm is capable of solving problems with 3,000,000 queens in approximately 55 seconds.