Fast search algorithms for the n-queens problem
Rok Sosič, J. Gu · IEEE Transactions on Systems Man and Cybernetics · 1991
The n-queens problem is to place n queens on an n*n chessboard so that no two queens attack each other. The authors present two new algorithms, called queen search 2 (QS2) and queen search 3 (QS3). QS2 and QS3 are probabilistic local search algorithms, based on a gradient-based heuristic. These algorithms, running in almost linear time, are capable of finding a solution for extremely large n-queens problems. For example, QS3 can find a solution for 500000 queens in approximately 1.5 min.>