TOPICS
Search

Rooks Problem


RooksMax

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 n×n chessboard is n. This arrangement is achieved by placing the rooks along the diagonal (Madachy 1979). The total number of ways of placing n nonattacking rooks on an n×n board is n! (Madachy 1979, p. 47). In general, the polynomial

 R_(mn)(x)=sum_(k)r_k^((m,n))x^k

whose coefficients r_k^((m,n)) give the numbers of ways k nonattacking rooks can be placed on an m×n chessboard is called a rook polynomial.

The number of rotationally and reflectively inequivalent ways of placing n nonattacking rooks on an n×n 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 8×8 chessboard is 8 (Madachy 1979), arranged in the same orientation as above.

Consider an n×n chessboard with the restriction that, for every subset of {1,...,n}, a rook may not be put in column s+j (mod n) when on row j, where the rows are numbered 0, 1, ..., n-1. Vardi (1991) denotes the number of rook solutions so restricted as rook(s,n). rook({1},n) is simply the number of derangements on n symbols, known as a subfactorial. The first few values are 1, 2, 9, 44, 265, 1854, ... (OEIS A000166). rook({1,2},n) 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 {1,...,p}, recurrence relations can be used to compute rook({1,...,p},n) in polynomial time for p=3, ..., 6 (Metropolis et al. 1969, Minc 1978, Vardi 1991).


See also

Chess, Married Couples Problem, Rook Number, Rook Polynomial, Rook Reciprocity Theorem

Explore with Wolfram|Alpha

References

Dudeney, H. E. "The Eight Rooks." §295 in Amusements in Mathematics. New York: Dover, pp. 88 and 96, 1970.Kraitchik, M. "The Problem of the Rooks" and "Domination of the Chessboard." §10.2 and 10.4 in Mathematical Recreations. New York: W. W. Norton, pp. 240-247 and 255-256, 1942.Madachy, J. S. Madachy's Mathematical Recreations. New York: Dover, pp. 36-37 and 46-54, 1979.Metropolis, M.; Stein, M. L.; and Stein, P. R. "Permanents of Cyclic (0, 1) Matrices." J. Combin. Th. 7, 291-321, 1969.Minc, H. §3.1 in Permanents. Reading, MA: Addison-Wesley, 1978.Riordan, J. Chs. 7-8 in An Introduction to Combinatorial Analysis. Princeton, NJ: Princeton University Press, 1978.Sloane, N. J. A. Sequences A000903/M1761, A000166/M1937, and A000179/M2062 in "The On-Line Encyclopedia of Integer Sequences."Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 123-124, 1991.Watkins, J. Across the Board: The Mathematics of Chessboard Problems. Princeton, NJ: Princeton University Press, 2004.

Referenced on Wolfram|Alpha

Rooks Problem

Cite this as:

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

Subject classifications