Rooks Problem

The rook is a Chess piece which may move any number of spaces either horizontally or vertically per move. Themaximum number of nonattacking rooks which may be placed on an Chessboard is . This arrangement isachieved by placing the rooks along the diagonal (Madachy 1979). The total number of ways of placing nonattackingrooks on an board is (Madachy 1979, p. 47). The number of rotationally and reflectively inequivalentways of placing nonattacking rooks on an board are 1, 2, 7, 23, 115, 694, ... (Sloane's 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 incolumn (mod ) when on row , where the rows are numbered 0, 1, ..., . Vardi (1991) denotes the number ofrook solutions so restricted as . is simply the number ofDerangements on symbols, known as a Subfactorial. The first few values are 1, 2, 9, 44,265, 1854, ... (Sloane's A000166). is a solution to the Married Couples Problem,sometimes known as Ménage Numbers. The first few Ménage Numbers are, 1, 0, 2, 13, 80, 579, ... (Sloane's A000179).

Although simple formulas are not known for general , ..., , Recurrence Relationscan be used to compute in polynomial time for , ..., 6 (Metropolis et al. 1969, Minc 1978, Vardi 1991).

References

Dudeney, H. E. ``The Eight Rooks.'' §295 in Amusements in Mathematics. New York: Dover, p. 88, 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, 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. SequencesA000903/M1761A000166/M1937, andA000179/M2062in ``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. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 123-124, 1991.

• Algorithm
• Algorithmic Complexity
• Alhazen's Billiard Problem
• Alhazen's Problem
• Aliasing
• Aliquant Divisor
• Aliquot Cycle
• Aliquot Divisor
• Aliquot Sequence
• Alladi-Grinstead Constant
• Allais Paradox
• Allegory
• Allometric
• All-Poles Model
• Almost All
• Almost Alternating Knot
• Almost Alternating Link
• Almost Everywhere
• Almost Integer
• Almost Perfect Number
• Almost Prime
• Alpha
• Alphabet
• Alpha Function
• Alphamagic Square