Sources page biographical material

5.Z. CHESSBOARD PLACING PROBLEMS
See MUS I 285-318, some parts of the previous chapter and the Appendix in II 351-360. See also 5.I.1, 6.T.

There are three kinds of domination problems.

In strong domination, a piece dominates the square it is on.

In weak domination, it does not, hence more pieces may be needed to dominate the board.

Non attacking domination is strong domination with no piece attacking another. Graph theorists say the pieces are independent. This also may require more pieces than strong domination, but it may require more or fewer pieces than weak domination.

The words 'guarded' or 'protected' are used for weak domination, but 'unguarded' or 'unprotected' may mean either strong or non attacking domination.

Though these results seem like they must be old, the ideas seem to have originated with the eight queens problem, c1850, (cf 5.I.1) and to have been first really been attacked in the late 19C. There are many variations on these problems, e.g. see Ball, and I will not attempt to be complete on the later variations. In recent years, this has become a popular subject in graph theory, where the domination number, γ(G), is the size of the smallest strongly dominating set on the graph G and the independent domination number, i(G), is the size of the smallest non-attacking (= independent) dominating set.

Mario Velucchi has a web site devoted to the non-dominating queens problem and related sites for similar problems. See: http://www.bigfoot.com/~velucchi/papers.html and http://www.bigfoot.com/~velucchi/biblio.html.

Ball. MRE, 3rd ed., 1896, pp. 109-110: Other problems with queens. Says: "Captain Turton has called my attention to two other problems of a somewhat analogous character, neither of which, as far as I know, has been hitherto published, ...." These ask for ways to place queens so as to attack as few or as many cells as possible -- see 5.Z.2.

Ball. MRE, 4th ed., 1905, pp. 119-120: Other problems with queens; Extension to other chess pieces. Repeats above quote, but replaces 'hitherto published' by 'published elsewhere', extends the previous text and adds the new section.

Ball. MRE, 5th ed., 1911. Maximum pieces problem; Minimum pieces problem, pp. 119 122. [6th ed., 1914 adds that Dudeney has written on these problems in The Weekly Dispatch, but this is dropped in the 11th ed. of 1939.] Considerably generalizes the problems. On the 8 x 8 board, the maximum number of non-attacking kings is 16, queens is 8, bishops is 14 [6th ed., 1914, adds there are 256 solutions], knights is 32 with 2 solutions and rooks is 8 with 8⁸ solutions [sic, but changed to 8! in the 6th ed.]. The minimum number of pieces to strongly dominate the board is 9 kings, 5 queens with 91 inequivalent solutions [the 91 is omitted in the 6th ed., since it is stated later], 8 bishops, 12 knights, 8 rooks. The minimum number of pieces to weakly dominate the board is 5 queens, 10 bishops, 14 knights, 8 rooks.

Dudeney. AM. 1917. The guarded chessboard, pp. 95 96. Discusses different ways pieces can weakly or non attackingly dominate n x n boards.

G. P. Jelliss. Multiple unguard arrangements. Chessics 13 (Jan/Jun 1982) 8 9. One can have 16 kings, 8 queens, 14 bishops, 32 knights or 8 rooks non attackingly placed on a 8 x 8 board. He considers mixtures of pieces -- e.g. one can have 10 kings and 4 queens non attacking. He tries to maximize the product of the numbers of each type in a mixture -- e.g. scoring 40 for the example.