Rooks Problem

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 number of rotationally and reflectively inequivalent ways of placing nonattacking rooks on an board 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.

Consider an chessboard with the restriction that, for every subset of , a rook may not be put in column (mod ) when on row , where the rows are numbered 0, 1, ..., . Vardi (1991) denotes the number of rook solutions so restricted as . is simply the number of derangements on symbols, known as a subfactorial. 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. The first few ménage numbers are 0, 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 for , ..., 6 (Metropolis et al. 1969, Minc 1978, Vardi 1991).

Wolfram Web Resources