Queens Problem

What is the maximum number of queens which can be placed on an $n\times n$ Chessboard such that no two attack one another? The answer is $n$ queens, which gives eight queens for the usual $8\times 8$ board (Madachy 1979). The number of different ways the $n$ queens can be placed on an $n\times 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, ... (Sloane's A000170, Madachy 1979). The number of rotationally and reflectively distinct solutions are 1, 0, 0, 1, 2, 1, 6, 12, 46, 92, ... (Sloane's 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).

The minimum number of queens needed to occupy or attack all squares of an $8\times 8$ board is 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\times n$ board for which every queen is attacked (``protected'') by at least one other.

$k$ Queens	$n\times n$	$N_p(k,n)$
2	4	3
3	5	37
3	6	1
4	7	5

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\times n$ board for which no two queens attack one another (they are ``not protected'').

$k$ Queens	$n\times n$	$N_u(k,n)$
1	2	1
1	3	1
3	4	2
3	5	2
4	6	17
4	7	1
5	8	91

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, ... (Sloane's 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, ... (Sloane's A006717), and 0 for Even $n$.

Chow and Velucchi give 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^k b^{n^2-k}$ in the Polynomial

$$p(a,b,n)=\cases{ (a+b)^{n^2}+2(a+b)^n(a^2+b^2)^{(n^2-n)/2} ... ... \quad +4(a+b)^n(a^2+b^2)^{(n^2-n)/2} \quad n {\rm\ odd}.\cr}$$

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, ... (Sloane's A001366). The results can be generalized to $k$ queens on an $n\times n$ board.

See also Bishops Problem, Chess, Kings Problem, Knights Problem, Knight's Tour, Rooks Problem

References

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.

Chow, T. and Velucchi, M. ``Different Dispositions in the Chessboard.'' http://www.cli.di.unipi.it/~velucchi/diff.txt.

Dudeney, H. E. ``The Eight Queens.'' §300 in Amusements in Mathematics. New York: Dover, p. 89, 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.

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.

Pólya, G. ``Über die `doppelt-periodischen' Lösungen des $n$-Damen-Problems.'' In Mathematische Unterhaltungen und Spiele (Ed. W. Ahrens). 1918.

Riven, I.; Vardi, I.; and Zimmerman, 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://sue.csc.uvic.ca/~cos/inf/misc/Queen.html.

Sloane, N. J. A. Sequences A001366, A000170/M1958, A006717/M3005, A007705/M4691, A002562/M0180 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and extended entry in Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Vardi, I. ``The $n$-Queens Problems.'' Ch. 6 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 107-125, 1991.

Velucchi, M. ``Non-Dominating Queens Problem.'' http://www.cli.di.unipi.it/~velucchi/queens.txt.