Recreational Mathematics > Games > Board Games > Chess >

History and Terminology > Disciplinary Terminology > Political Terminology >

Interactive Entries > Interactive Demonstrations >

Queens Problem

What is the maximum number of queens that can be placed on an chessboard such that no two attack one another? The answer is queens for or and queens otherwise, which gives eight queens for the usual board (Madachy 1979; Steinhaus 1999, p. 29). The number of different ways the queens can be placed on an chessboard so that no two queens may attack each other for the first few 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 are illustrated above, and the remaining 80 are generated by rotation and reflection (Madachy 1979, Steinhaus 1999).

The minimum number of queens needed to occupy or attack all squares of an chessboard (i.e., domination numbers for the queen graphs) are given for , 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 .

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

queens
2	4	3
3	5	37
3	6	1
4	7	5
5	8	4860

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

queens
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 queens with 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 queens with odd are 1, 3, 15, 133, 2025, 37851, ... (OEIS A006717), and 0 for even .

Velucchi gives the solution to the question, "How many different arrangements of queens are possible on an order chessboard?" as 1/8th of the coefficient of 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 queens on an order chessboard to leave a maximum number 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 queens on an board.

Queens Problem

Wolfram Web Resources