A polynomial time algorithm for the N-Queens problem

ABSTRACT

The n-queens problem is a classical combinatorial problem in the artificial intelligence (AI) area. Since the problem has a simple and regular structure, it has been widely used as a testbed to develop and benchmark new AI search problem-solving strategies. Recently, this problem has found practical applications in VLSI testing and traffic control. Due to its inherent complexity, currently even very efficient AI search algorithms developed so far can only find a solution for the n-queens problem with n up to about 100. In this paper we present a new, probabilistic local search algorithm which is based on a gradient-based heuristic. This efficient algorithm is capable of finding a solution for extremely large size n-queens problems. We give the execution statistics for this algorithm with n up to 500,000.

REFERENCES

• 1: W. Ahrens. <i>Mathematische Unterhaltungen und Spiele (in German).</i> B.G. Teubner (Publishing Company), Leipzig, 1918--1921.
• 2: R. Dechter , J. Pearl, Network-based heuristics for constraint-satisfaction problems, Artificial Intelligence, v.34 n.1, p.1-38, Dec. 1987 [doi>10.1016/0004-3702(87)90002-6]
• 3: John Gary Gaschnig, Performance measurement and analysis of certain search algorithms., 1979
• 4: R. M. Haralick and G. Elliot. Increasing Tree Search Efficiency for Constraint Satisfaction Problems. <i>Artificial Intelligence,</i> 14:263--313, 1980.
• 5: Panel Discussion: Parallel Processing for Non-Numeric Applications. International Conference on Parallel Processing, Chicago, August 15, 1990.
• 6: L.E. Moses and R.V. Oakford. <i>Tables of Random Permutations.</i> Stanford University Press, Palo Alto, California, 1963.
• 7: Bernard A. Nadel, Representation Selection for Constraint Satisfaction: A Case Study Using n-Queens, IEEE Expert: Intelligent Systems and Their Applications, v.5 n.3, p.16-23, June 1990 [doi>10.1109/64.54670]
• 8: R. Sosic and J. Gu. <i>Fast N-queen Search on VAX and Bobcat Machines.</i> AI Project Report, Feb. 1988.
• 9: R. Sosic and J. Gu. <i>How to Search For Million Queens.</i> Technical Report UUCS-TR-88--008. Dept. of Computer Science, Univ. of Utah. Feb. 1988.
• 10: Harold S Stone , Paolo Sipala, The average complexity of depth-first search with backtracking and cutoff, IBM Journal of Research and Development, v.30 n.3, p.242-258, May 1986
• 11: Harold S. Stone , Janice M. Stone, Efficient search techniques—an empirical study of the N-Queens problem, IBM Journal of Research and Development, v.31 n.4, p.464-474, July 1, 1987

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Measurement, Performance