Las Vegas does n-queens

ABSTRACT

This paper presents two Las Vegas algorithms to generate single solutions to the n-queens problem. One algorithm generates and improves on random permutation vectors until it achieves one that is a successful solution, while the other algorithm randomly positions queens within each row in positions not under attack from above.

REFERENCES

• 1: E. J. Hoffman, J. C. Loessi and R. C. Moore, "Constructions for the Solution of the m Queens Problem", Mathematics Magazine, Vol. 42, No. 2 (Mar. 1969), p. 66--72. The construction is that of A. M. Yaglom and I. M. Yaglom, Neelementarnye Zadachi v Elementarnom Izlozhenii (Moscow, 1954), translated by James McCawley, Jr., revised and edited by Basil Gordon, Challenging Mathematical Problems with Elementary Solutions: Volume I, Combinatorial Analysis and Probability Theory (1964, reprinted by Dover 1987), pp. 92--98.
• 2: Bo Bernhardsson, Explicit solutions to the N-queens problem for all N, ACM SIGART Bulletin, v.2 n.2, p.7, April 1991 [doi>10.1145/122319.122322]
• 3: Rok Sosic , Jun Gu, A polynomial time algorithm for the N-Queens problem, ACM SIGART Bulletin, v.1 n.3, p.7-11, Oct. 1990 [doi>10.1145/101340.101343]
• 4: Rok Sosič and Jun Gu, "Fast Search Algorithms for the N-Queens Problem", IEEE Transactions on Systems, Man, and Cybernetics, Vo. 21, No. 6 (Nov/Dec 1991), pp. 1572--76.
• 5: http://www.acmcontest-pacnw.org/ProblemSet/2005/Problem I.
• 6: Niklaus Wirth, Program development by stepwise refinement, Communications of the ACM, v.14 n.4, p.221-227, April 1971 [doi>10.1145/362575.362577]
• 7: Niklaus Wirth, Algorithms & data structures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 8: http://penguin.ewu.edu/~trolfe/QueenLasVegas/

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms, Theory

Keywords:
Las Vegas algorithm, n-queens problem, probabilistic algorithm