çArrangements
This page has been reproduced September 2010, from the online Games and Puzzles Journal
site with minimal alteration.
|
The Games and Puzzles
Journal — Issue 38, March-April 2005 |
Chess-Piece Arrangement Problems
by George Jelliss
Part 3: — Coverings using one type of piece.
Sections on this page: —
(1) Introduction —
(2) Leapers (e.g. Knight, King) —
(3) Riders (e.g. Rook) —
(4) Compound Riders (e.g. Queen) —
(5) Other pieces (e.g. Grasshopper) —
End.
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.
Wazir: {0,1}-leaper.
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.
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".
Dabbaba: {0,2}-leaper. T. R. Dawson, Cheltenham Examiner May 1913 gave these two results: 16 to span the chessboard: 56,56,12,12,78,78,34,34 and 24 to dominate: ab3456,fg12345678.
Knight: {1,2}-leaper. 14 knights will dominate the chessboard: b6,c2356,d35,e35,f2356,g6 (Max Lange 1856), b35,c357,d37,e37,f357,g35 (T. R. Dawson 1908), b3,c34567,e3467,f37,g35 (F. Baird 1908).
This problem appears in Chess Amateur December 1908 (solution February 1909) where H. E. Dudeney shows that these three solutions are the only ones possible.
It also requires 14 knights to span the chessboard: a134,c167,d6,e3,f238,h568, where the pieces on a3, h6 can be moved to b1, g8 at will (G.P.Jelliss 9 May 1992).
However, only 12 knights are needed for a minimal covering of the 8 by 8 board, as shown in the third diagram above where 4 knights are guarded and eight unguarded.
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.
Camel: {1,3} leaper. 12 to dominate: b5,d2456,e234567,f5; bcfg5,de2456; b4,c5,d3457,e2456,f4,g5; de234567; T.R.Dawson L'Echiquier March 1927. These four forms are made by combining two cases of guards on squares of one colour.
King: Wazir + Fers. 9 will span the chessboard: a258,d258,g258 (Rouse Ball), this is the minimal covering.
It takes 12 to dominate the chessboard: b2367,e2367,g2367.
Alibaba: {0,2} + {2,2} leaper. 16 to cover, span (as for unguard arrangements) or dominate (e.g. cdef3456, i.e. filling the central 4×4 area).
Fiveleaper: {0,5}+{3,4} mover. 16 to dominate the chessboard; ae1458,cg2367 (G. P. Jelliss 1970s). There are two forms of arrangement of 8 fiveleapers to guard squares of one colour. These combine to give three forms (toral rotations of the one given here).
Rook; {0,1}-rider. The minimum number of rooks needed to span a square board of side n is n. To prove this consider a rank or file that contains no rook, then to guard all the cells on this line requires one rook on each of the perpendicular lines. If on the other hand there is no such line then there must be at least one rook in every rank and file, and this requires at least n rooks.
The solutions to the minimal spanning problem are in the case of rooks the same as the solutions to the maximal unguard problem, i.e. the n! satins.
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.
Bishop: {1,1}-rider. 8 will span the chessboard: d12345678 (Rouse Bal).
10 will dominate the chessboard: c36d45,e2457,g45, bcdfg45 (Rouse Ball).
Nightrider: {1,2}-rider. 8 nightriders are sufficient to span or dominate the chessboard:
But 6 is all that are needed to span an 8×8 torus: b6,e6,f2,f5,f7,g6 or b2,e6,f5,f6,f7,g6 (by A. S. M. Dickins, feenschach 1967).
Queen; Rook + Bishop.
1×1: 1Q to span or cover.
2×2: 1Q to span or cover; 2Q to dominate.
3×3: 1Q to span or cover, G = 1: b2; 2Q to dominate.
4×4: 3Q to span, G = 2: a4b1c3, a4b1d2, T = 16; but only 2Q to dominate, G = 3, a1c3, a2d2, b2b3, T = 12 (Rouse Ball). So in this case the minimal covering is by domination rather than spanning.
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.
Raven. Rook + Nightrider. 4 to dominate. Three solutions were found by solvers in Fairy Chess Review: c58f23 (T.R.Dawson), a4b2e7f7 (A.W.Baillie and P.C.Taylor), c28f35 (J.Peacock).
I find it takes 5 (R+N)s to span the chessboard. From the first diagram two other similar positions can be formed by toral rotation of the board one rank up (so piece h8 reappears at h1) or one file right (so piece h8 reappears at a8).
The three (R+N)-formation common to all these solutions span a 6 by 6 board.
Banshee: Bishop + Nightrider It takes 6 B+N to span the chessboard. I have found three solutions: ceg36 (diagram), and the similar bcg36 and cgh36 (where the two pieces in the e file are moved to the b or h file respectively).
I have noted 8 ways in which 5(B+N) can guard 63 cells of the chessboard (there are probably more), 4 are shown below, where the white king marks the unguarded cell. Four others can be derived from the third diagram by moving (B+N)f5 to f2 or g4, or (with WK c8) to e3 or b3.
It seems 6 (B+N)s are needed to dominate the board (though I don't have a full proof of this), and there are thus many solutions.
Amazon: Queen + Knight. On the 8 by 8 board 4 can span: a2b8g1h7, and 4 can dominate: a1d7g4h8.
But it only takes 3 to cover: a1d7g4 (all three results by T.R.Dawson, L'Echiquier Sept-Oct 1930).
Grasshoppers. Moves along queen lines over one piece to the first cell beyond the hurdle. 8×8 board: 18 to dominate: bg2467,cf25,de247 or Ge2 can be moved to f3 (O. E. Vinje Fairy Chess Review November 1939).
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.
Back to: Arrangements
