Chess-Piece Arrangement Problems

Part 3: — Coverings using one type of piece.

The Covering Problem is to place pieces of a given type on a given board so as to guard and/or occupy all the cells. The pieces are said to cover the board. If the pieces are all unguarded we say the pieces span the board. If the pieces are all guarded (so that all the cells of the board are guarded) we say the pieces dominate the board. If some pieces are guarded and some not we call the arrangement a mixed covering. Since the spanning and dominating problems add an extra condition to the covering problem they may sometimes need more pieces than are needed for a minimal covering. To distinguish these cases we show guarded pieces as black and unguarded as white. Where we show diagrams with small squares, so as to fit in more data, we show the occupied cells as black and white. For fuller explanations of methods of enumeration and description of symmetry refer back to the Introduction to Part 1.

As is usual in chess publications we letter the files a, b, c, ... and number the ranks 1, 2, 3, ... from the bottom left cell. Where there is no more than one piece in a file, a solution can often be presented concisely on boards up to 9 files, by a series of digits giving the ranks occupied by the pieces in the successive files, an empty file being denoted by 0. We adopt the convention of orienting the board so that the number obtained in this way is the smallest possible, and we then present the solutions in numerical sequence.

The 8×8 case was studied by T.R.Dawson. In Cheltenham Examiner April 1913 he showed how 16 wazirs will span the chessboard: 26,48,15,37,26,48,15,37, and 20 will dominate it: 25,2578,5,123,678,4,1247,47. In Chess Amateur July and September 1929 he showed that there are 8 arrangements of 10 wazirs guarding all the dark cells. These can be combined with similar arrangements on the light cells in 33 geometrically different patterns. The 8 half-patterns are: 4,17,6,3,8,15,0,37; 48,1,6,3,8,15,0,37; 4,17,0,35,8,15,0,37; 4,17,4,0,268,0,24,7; 4,17,4,0,268,0,4,17; 6,13,8,5,2,7,24,7; 6,13,8,5,2,7,4,17; 4,17,4,7,2,5,28,5. Mixed coverings with 16 wazirs are also possible for example: 36,18,45,27,27,45,18,36 or 36,18,45,27,5,138,6,247.

16 wazirs span

20 wazirs dominate

20 fers span

16 fers dominate

Fers: {1,1}-leaper.

For the 8×8 case it takes 20 to span the chessboard: 27,2457,0,1368,1368,0,2457,27 (G.P.Jelliss 3 February 1985) and 16 to dominate the chessboard: bcfg2367, which is thus the minimal covering. This 16-fers position was given in a manuscript of c.1370, as quoted by D. Hooper and K. Whyld in The Oxford Companion to Chess 1984, p.16, article on "Arrangement".

See http://www.contestcen.com/knight.htm by Frank Rubin for solutions on boards up to 26×26. He gives one solution for each square case.

An 8 by 8 torus board can be dominated by only 8 knights: a23,c58,e67,g14.

The domination problem also solves with n rooks (except for n = 1 when the task is of course impossible, since a rook cannot guard itself), for example they can all be put in the same rank. Since all the rooks are to be guarded there must be at least two in one rank (or file), guarding each other. This means that there must be at least one rank (or file) with no rooks in it. But all the cells in this vacant rank (or file) must be guarded. Therefore there must be one rook in each file (or rank). Take the case of one in each file. To enumerate the solutions it is necessary to consider the possible partitions of the rooks among the ranks. All in one rank: n cases. With n–2 in one and 2 in another: n(n–1)(nC2) cases. With n–3 in one and 3 in another: n(n–1)(nC3) cases. And so on. Where rCs = r!/(r–s)!s! is the number of ways of choosing a set of s out of a set of r.

On the 8-square board the partitions and totals are:

8	8C1 = 8
6:2	2.8C2.8C2 = 1568
5:3	2.8C2.8C3 = 3136
4:4	8C2.8C4 = 1960
4:2:2	8C1.7C2.8C2.6C2 = 70560
3:3:2	8C1.7C2.8C2.6C3 = 94080
2:2:2:2	8C4.8C2.6C2.4C2 = 176400
Total with one in each file	346712
Double to count the ranks as well as the files.	693424

Here are two examples of domination and two of covering: For the minimal covering problem, again the answer is n rooks. All the spanning and dominating solutions also of course solve this case, but there are additional solutions too. The number of ways of arranging n rooks with one in every rank is n^n, and the same number of ways applies for one rook in each file. These two counts however are not independent: the satin arrangements, which have one rook in each file and one in each rank, are counted in both camps. Thus the total number of coverings of the n-square board with the minimum n rooks is 2(n^n) – n!

On the 8 by 8 board this is 33,514,212. If we subtract the unguarded (40,320) and guarded (693,424) this still leaves us with 32,780,368 cases part-guarded, part-unguarded.

5×5:
3Q to span, G = 2: a1b4d3, a1c4e3, T = 16.

3Q to dominate, G = 15 (3 biaxial, 8 axial, 4 asymmetric), T = 3×2 + 8×4 + 4×8 = 70.

3Q to cover, G = 37 of which 2 span, 15 dominate, 20 are mixed, T = 186.

6×6:
4Q to span, G = 17: 104603, 136002, 140502, 140520, 160025, 160304, 201405, 201605, 205104, 206104, 241005, 250014, 250630, 260015, 261005, 306104, 261040, T = 8x14 + 4x1 + 2x2 = 120. This problem is in Jaenisch (1862), but he counts 21 solutions, whereas H. E. Dudeney Canterbury Puzzles (solution to problem 92, p.237-8), counted 17, which is correct.
4Q to dominate: b2b5e2e5. To cover, however, only 3Q are needed: G = 1, a1c5e3, T = 4. This is the first case where a covering can be achieved with fewer queens than are needed to span or to dominate. (H. E. Dudeney Canterbury Puzzles solution to problem 92, p.238).

7×7: 4Q to span or cover, G = 1: a2b6d1e5, T = 8; 5Q to dominate, e.g. a2b3b6d1g4.

8×8:
5Q to span, G = 91 (total given by Rouse Ball), e.g. c6d3e5f7g4, a1b3c7f2g6
5Q to dominate, e.g. b7d5e4f3h1, b4c4d4e4h4 (Rouse Ball).
5Q to cover. Four queens can guard or occupy 62 of the 64 cells, leaving considerable scope for placing the fifth queen, e.g. a3b7e2f6 (no guard g1g8), a1c7e3g5 (no guard b4f8), a1f4d5e6 (no guard c2h7). (T. R. Dawson Sphinx October 1935). Professor von Szily is said to have shown that there are 4860 = 61×4 + 577×8 solutions and 638 = 61 + 577 forms.

Greater Grasshoppers. GGs hop in any direction (i.e. along rook, bishop, nightrider, camelrider, zebrarider lines) to the first cell, in that line, beyond the hurdle. 8×8 board: 16 to dominate: (A) bdeg36,cf2457; (B) b35,c456,d236,e367,f345,g46; (C) a4,b45,c4,d2678,e1237,f5,g45,h5; (D) b35,c246,d357,e246,f357,g46.