N-Queens, Constraint Satisfaction, Local Search

Contents

  1. A Story about the N-Queens Problem:
    From Exponential to (Almost) Constant Time
  2. Constraint Satisfaction Problem
  3. Local Search Optimization
  4. Bibliography

A Story about the N-Queens Problem:
From Exponential to (Almost) Constant Time

The n-queens problem is to place n queens on an N X N chessboard, so that no two queens attack each other. An extensive bibliography on the problem is available here. The n-queens problem is a classical search problem, used as a testbed for the development and benchmarking of search algorithms. Traditional search methods involve backtracking. Because the complexity of backtracking usually rises exponentially with the size of the problem, it is desirable to develop alternatives to backtracking search. To overcome the weaknesses of backtracking, we have started to develop local search methods in late 1987, using the n-queens problem as a testbed. At that time, the best backtracking methods could find a solution for the problem sizes of around 100.

The first local search algorithm was able to find a solution for the problem size of 500,000 in around 10,000s on a Next computer. A description of the algorithm can be found in R. Sosic and J. Gu. A Polynomial Time Algorithm for the N-Queens Problem. SIGART Bulletin, Vol. 1, 3, pp. 7-11, Oct, 1990. (retrieve an abstract or a Postscript version)

The algorithm was further improved, which reduced the search time to 94s on a Next computer. A description of improvements and an analysis of the algorithm behavior can be found in R. Sosic and J. Gu. Fast Search Algorithms for the N-Queens Problem. IEEE Transactions on Systems, Man, and Cybernetics. Vol. 21, 6, pp. 1572-1576, Nov/Dec, 1991. (retrieve an abstract or a Postscript version)

The final version of the algorithm is capable of solving the n-queens problem in a linear time. On an IBM RS6000, it takes around 55s to find a solution to the problem size of 3,000,000. An initial description of the algorithm can be found in R. Sosic and J. Gu. 3,000,000 Queens in Less Than One Minute. SIGART Bulletin, Vol. 2, 2, pp. 22-24, Apr, 1991. (retrieve an abstract or a Postscript version) A detailed description and an in-depth analysis of the algorithm can be found in R. Sosic and J. Gu. Efficient Local Search with Conflict Minimization: A Case Study of the N-Queens Problem. IEEE Transactions on Knowledge and Data Engineering, Vol. 6, 5, pp. 661-668, Oct 1994. (retrieve an abstract or a Postscript version)

The next stage was the development of a parallel version of the algorithm. The algorithm performs a probabilistic parallel search and by using n processors, its running time is O(log^2n). With some tunning, the algorithm can find a solution in a constant number of steps - 12 - in a PRAM model. A description and analysis of the algorithm can be found in R. Sosic. A Parallel Search Algorithm for the N-Queens Problem. Parallel Computing and Transputer Conference, Wollongong, pp. 162-172, IOS Press, Nov 1994. (retrieve an abstract or a Postscript version)

Constraint Satisfaction Problem

The n-queens problem has been studied in relationship to the research on the constraint satisfaction problem. The goal of the research is to develop fast and practical solutions to large scale constraint satisfaction problems.

Some results of this research can be found in J. Gu and R. Sosic. A Parallel, Optimal Arc Consistency Algorithm. 1990 International Conference on Parallel Processing, pp. I-599-600, 1990. and J. Gu and R. Sosic. A Parallel Architecture for Constraint Satisfaction. International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, June 1991, Kauai, Hawaii, pp. 229-237, 1991. (retrieve an abstract or a Postscript version)

Local Search Optimization

Local search methods are often approximative. The improvement in the quality of the solution requires more computational time. One of the questions is how long an algorithm should run for a given quality of solution. An initial investigation of this question is presented in R. Sosic and G. Wilby. Using the Quality-Time Tradeoff in Local Optimization. IEEE Second ANZIIS Conference, Brisbane, pp. 253-257, IEEE, Dec 1994. (retrieve an abstract or a Postscript version)

Bibliography

R. Sosic and G. Wilby. Using the Quality-Time Tradeoff in Local Optimization. IEEE Second ANZIIS Conference, Brisbane, pp. 253-257, IEEE, Dec 1994. (retrieve an abstract or a Postscript version)

R. Sosic. A Parallel Search Algorithm for the N-Queens Problem. Parallel Computing and Transputer Conference, Wollongong, pp. 162-172, IOS Press, Nov 1994. (retrieve an abstract or a Postscript version)

R. Sosic and J. Gu. Efficient Local Search with Conflict Minimization: A Case Study of the N-Queens Problem. IEEE Transactions on Knowledge and Data Engineering, Vol. 6, 5, pp. 661-668, Oct 1994. (retrieve an abstract or a Postscript version)

R. Sosic and J. Gu. Fast Search Algorithms for the N-Queens Problem. IEEE Transactions on Systems, Man, and Cybernetics. Vol. 21, 6, pp. 1572-1576, Nov/Dec, 1991. (retrieve an abstract or a Postscript version)

J. Gu and R. Sosic. A Parallel Architecture for Constraint Satisfaction. International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, June 1991, Kauai, Hawaii, pp. 229-237, 1991. (retrieve an abstract or a Postscript version)

R. Sosic and J. Gu. 3,000,000 Queens in Less Than One Minute. SIGART Bulletin, Vol. 2, 2, pp. 22-24, Apr, 1991. (retrieve an abstract or a Postscript version)

R. Sosic and J. Gu. A Polynomial Time Algorithm for the N-Queens Problem. SIGART Bulletin, Vol. 1, 3, pp. 7-11, Oct, 1990. (retrieve an abstract or a Postscript version)

J. Gu and R. Sosic. A Parallel, Optimal Arc Consistency Algorithm. 1990 International Conference on Parallel Processing, pp. I-599-600, 1990.

sosic@cit.gu.edu.au, 18 April 1995