The rooks problem asks for the maximum number of nonattacking rooks on an 
chessboard and the number
of such placements. The rook is a chess piece that may
move any number of spaces either horizontally or vertically per move. The maximum
number of nonattacking rooks that may be placed on an 
chessboard is 
. This arrangement is achieved by placing the rooks
along the diagonal (Madachy 1979). The total number of ways of placing 
nonattacking rooks on an 
board is 
(Madachy 1979, p. 47). In general, the polynomial
 |
whose coefficients 
give the numbers of ways 
nonattacking rooks can be placed on an 
chessboard is called
a rook polynomial.
The numbers of rotationally and reflectively inequivalent ways of placing 
nonattacking rooks on an 
board for 
, 3, ... are 1, 2, 7, 23, 115,
694, ... (OEIS A000903; Dudeney 1970, p. 96;
Madachy 1979, pp. 46-54).
The minimum number of rooks needed to occupy or attack all spaces on an 
chessboard is 8 (Madachy
1979), arranged in the same orientation as above.
For a fixed subset 
of 
, consider an 
chessboard with the
restriction that, for every 
, a rook may not be put in
column 
(mod 
) when on row 
. Rows and columns are numbered
0, 1, ..., 
. Vardi (1991) denotes the number of placements of
nonattacking rooks so restricted as 
. 
is simply the number of derangements
on 
symbols, known as a subfactorial.
For 
, 3, ..., the first few values are 1, 2, 9, 44, 265,
1854, ... (OEIS A000166). 
is a solution to the married
couples problem, sometimes known as ménage numbers. For 
, 3, ..., the first few ménage numbers are
0, 1, 2, 13, 80, 579, ... (OEIS A000179).
Although simple formulas are not known for general 
, recurrence
relations can be used to compute 
in polynomial time in 
for each fixed 
, ..., 6 (Metropolis et al.
1969, Minc 1978, Vardi 1991).
