TOPICS
Search

Queens Problem


QueensMax

What is the maximum number of queens that can be placed on an n×n chessboard such that no two attack one another? The answer is n-1 queens for n=2 or n=3 and n queens otherwise, which gives eight queens for the usual 8×8 board (Madachy 1979; Steinhaus 1999, p. 29). The number of different ways the n queens can be placed on an n×n chessboard so that no two queens may attack each other for the first few n are 1, 0, 0, 2, 10, 4, 40, 92, ... (OEIS A000170; Madachy 1979; Steinhaus 1999, p. 29). The number of rotationally and reflectively distinct solutions of these are 1, 0, 0, 1, 2, 1, 6, 12, 46, 92, ... (OEIS A002562; Dudeney 1970; p. 96). The 12 distinct solutions for n=8 are illustrated above, and the remaining 80 are generated by rotation and reflection (Madachy 1979, Steinhaus 1999).

QueensMin

The minimum number of queens needed to occupy or attack all squares of an n×n chessboard (i.e., domination numbers for the n×n queen graphs) are given for n=1, 2, ... by 1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 10, ... (OEIS A075458), where Steinhaus 1999 (p. 29) notes gamma(Q_(8,8))=5.

Dudeney (1970, pp. 95-96) gave the following results for the number of distinct arrangements N_p(k,n) of k queens attacking or occupying every square of an n×n board for which every queen is attacked ("protected") by at least one other, with the n=8 value given by Steinhaus (1999, p. 29). The 4860 solutions in the n=5 case may be obtained from 638 fundamental arrangements by rotation and reflection.

k queensn×nN_p(k,n)
243
3537
361
475
584860

Dudeney (1970, pp. 95-96) also gave the following results for the number of distinct arrangements N_u(k,n) of k queens attacking or occupying every square of an n×n board for which no two queens attack one another (they are "not protected").

k queensn×nN_u(k,n)
121
131
342
352
4617
471
5891

Vardi (1991) generalizes the problem from a square chessboard to one with the topology of the torus. The number of solutions for n queens with n odd are 1, 0, 10, 28, 0, 88, ... (OEIS A007705). Vardi (1991) also considers the toroidal "semiqueens" problem, in which a semiqueen can move like a rook or bishop, but only on positive broken diagonals. The number of solutions to this problem for n queens with n odd are 1, 3, 15, 133, 2025, 37851, ... (OEIS A006717), and 0 for even n.

Velucchi gives the solution to the question, "How many different arrangements of k queens are possible on an order n chessboard?" as 1/8th of the coefficient of a^kb^(n^2-k) in the polynomial

 p(a,b,n)={(a+b)^(n^2)+2(a+b)^n(a^2+b^2)^((n^2-n)/2);   +3(a^2+b^2)^(n^2/2)+2(a^4+b^4)^(n^2/4);  n even; (a+b)^(n^2)+2(a+b)(a^4+b^4)^((n^2-1)/4);   +(a+b)(a^2+b^2)^((n^2-1)/2);   +4(a+b)^n(a^2+b^2)^((n^2-n)/2)  n odd.
(1)

Velucchi also considers the nondominating queens problem, which consists of placing n queens on an order n chessboard to leave a maximum number U(n) of unattacked vacant cells. The first few values are 0, 0, 0, 1, 3, 5, 7, 11, 18, 22, 30, 36, 47, 56, 72, 82, ... (OEIS A001366). The results can be generalized to k queens on an n×n board.


See also

Bishops Problem, Chess, Kings Problem, Knights Problem, Knight Graph, Rooks Problem

Explore with Wolfram|Alpha

References

Ahrens, W. "Das Achtköniginnenproblem." Ch. 9 in Mathematische Unterhaltungen und Spiele, dritte, verbesserte, anastatisch gedruckte aufl., Bd. 1. Leipzig, Germany: Teubner, pp. 211-284, 1921.Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 166-169, 1987.Campbell, P. J. "Gauss and the 8-Queens Problem: A Study in the Propagation of Historical Error." Historia Math. 4, 397-404, 1977.Chatham, D. "The N+k Queens Problem Page." http://people.moreheadstate.edu/fs/d.chatham/n+kqueens.html.Dudeney, H. E. "The Eight Queens." §300 in Amusements in Mathematics. New York: Dover, pp. 89 and 95-96, 1970.Erbas, C. and Tanik, M. M. "Generating Solutions to the N-Queens Problem Using 2-Circulants." Math. Mag. 68, 343-356, 1995.Erbas, C.; Tanik, M. M.; and Aliyzaicioglu, Z. "Linear Congruence Equations for the Solutions of the N-Queens Problem." Inform. Proc. Let. 41, 301-306, 1992.Gardner, M. "Patterns in Primes Are a Clue to the Strong Law of Small Numbers." Sci. Amer. 243, 18-28, Dec. 1980.Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1983.Ginsburg, J. "Gauss's Arithmetization of the Problem of n Queens." Scripta Math. 5, 63-66, 1939.Guy, R. K. "The n Queens Problem." §C18 in Unsolved Problems in Number Theory, 2nd ed. New York:Springer-Verlag, pp. 133-135, 1994.Kraitchik, M. "The Problem of the Queens" and "Domination of the Chessboard." §10.3 and 10.4 in Mathematical Recreations. New York: W. W. Norton, pp. 247-256, 1942.Madachy, J. S. Madachy's Mathematical Recreations. New York: Dover, pp. 34-36, 1979.Östergård, P. R. J. and Weakley, W. D. "Values of Domination Numbers of the Queen's Graph." Electronic J. Combinatorics 8, No. 1, R29, 1-19, 2001. http://www.combinatorics.org/Volume_8/Abstracts/v8i1r29.html.Pegg, E. Jr. "Math Games: Chessboard Tasks." Apr. 11, 2005. http://www.maa.org/editorial/mathgames/mathgames_04_11_05.html.Riven, I.; Vardi, I.; and Zimmermann, P. "The n-Queens Problem." Amer. Math. Monthly 101, 629-639, 1994.Riven, I. and Zabih, R. "An Algebraic Approach to Constraint Satisfaction Problems." In Proc. Eleventh Internat. Joint Conference on Artificial Intelligence, Vol. 1, August 20-25, 1989. Detroit, MI: IJCAII, pp. 284-289, 1989.Ruskey, F. "Information on the n Queens Problem." http://www.theory.csc.uvic.ca/~cos/inf/misc/Queen.html.Sloane, N. J. A. Sequences A000170/M1958, A001366, A002562/M0180, A006717/M3005, A007705/M4691, and A075458 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M0180 in The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 29-30, 1999.Vardi, I. "The n-Queens Problems." Ch. 6 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 107-125, 1991.Velucchi, M. "For Me, This Is the Best Chess-Puzzle: Non-Dominating Queens Problem." http://anduin.eldar.org/~problemi/papers.html.Velucchi, M. "Different Dispositions on the ChessBoard." http://anduin.eldar.org/~problemi/papers.html.Watkins, J. Across the Board: The Mathematics of Chessboard Problems. Princeton, NJ: Princeton University Press, 2004.

Cite this as:

Weisstein, Eric W. "Queens Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/QueensProblem.html

Subject classifications