Chess-Piece Arrangement Problems

Part 2: — Unguard Arrangements of Riders (and some other pieces).

This issue is the second devoted to new and collected results on chess-piece arrangement problems. Part 1 covered unguard arrangements using one type of leaper. Here we extend that study to unguard problems using other types of piece. The unguard problem is to place the maximum number of pieces so that none guards any other. See Part 1 for further general comments about how the solutions are counted and symmetries are described.

A convention that is often helpful to distinguish similar cases is to show guarded pieces as black and unguarded as white. Where diagrams are shown with small squares, so as to fit in more data, the vacant cells are grey and the occupied cells white (since in unguard problems no pieces are guarded).

On boards up to 9 by 9 a solution can be represented by a series of digits giving the ranks occupied by the pieces in the successive files, an empty file being denoted by 0.

Since the rook in the first file can be placed in n ways, and then the rook in the second file in n–1 ways, and so on, we have the total number of arrangements: T(n) = n×(n–1)×(n–2)×...×3×2×1 = n! [where ! denotes the factorial operator].

The question of how many geometrically distinct satins G(n) there are of size n is a difficult problem. This was considered by Maurice Kraitchik in his column in L'Echiquier (1925) and later in his book on Mathematical Recreations (1953 p.245). This work was completed by D. Holt in his article “Rooks Inviolate” Mathematical Gazette (1974 pp.131-4). The values in the following table, and the notes below, are from my article on satin squares in The Games and Puzzles Journal 1988 pp.82-83.

n	1	2	3	4	5	6	7	8	9
T(n)	1	2	6	24	120	720	5040	40320	362880
G(n)	1	1	2	7	23	115	694	5282	46066

The chart below shows all the geometrically distinct satins of sizes 1 to 5.

The files represent the weft threads, the ranks the warp threads, and the white cells indicate where the warp passes over the weft (or vice versa).

Mathematicians will recognise that if the pieces are 1s and vacant cells are 0s the array is a permutation matrix (which when used to multiply another array, under the usual definition of matrix multiplication, permutes its ranks or files).

A useful theorem, attributed variously to W. Burnside or G. Polya, states that the number of geometrically distinct patterns of a given type in a shape unaltered by a Group of k symmetry operations S1, S2, ..., Sk is (N1 + N2 + ... + Nk)/k, where Nr is the number of cases unaltered by operation Sr. One of these operations, which we may take to be S1, must be the identity operation; thus N1 is the total number of cases without regard to symmetry.

In the case of a square pattern there are 8 symmetry operations: S1 – S4 being rotations through 0, 1, 2 and 3 right angles (clockwise); and S5 – S8 being equal to S1 – S4 combined with transposition (i.e. reflection in the principal diagonal, top left to bottom right). The 1×1 satin is the only one unaltered by reflection in the horizontal, S6, or reflection in the vertical, S8. For all other cases (n > 1) we have N6 = N8 = 0. We always have N2 = N4 (cases unaltered by 90 degree rotation clockwise or anticlockwise), and N5 = N7 (cases unaltered by reflection in principal or secondary diagonal).

Thus the formula becomes G(n) = (n! + 2×N2 + N3 + 2×N5)/8 for n > 1, where N2, N3 and N5 are functions of n. Kraitchik and Holt proved the following recursion relations which enable us to calculate successive values of G(n), as tabulated above.

N2 (Holt): N2(n) = N2(n–1) + (n–1)×N2(n–2)

N3 (Kraitchik): N3(2k+1) = N3(2k) = 2k×N3(2k–2)

N5 (Kraitchik): N5(4k) = N5(4k+1) = (4k–2)×N5(4k–4), N5(4k+2) = N5(4k+3) = 0.

On the 8 by 8 board we can place 7 bishops on the light cells in 2^4 = 16 ways and combine with another 7 on the dark cells, giving 16^2 = 2^8 = 256 ways.

n	1	2	3	4	5	6	7	8	9
T(n)	1	4	8	2	10	4	40	92	352
G(n)	1	1	1	1	2	1	6	12	46

Here is a list of the solutions up to size 7:

(1) 1, (2) 01, (3) 013, (4) 2413 symmetric, (5) 13524, 25314 symmetric, (6) 246135 symmetric,
(7) 1357246, 1473625, 2417536, 2514736 symmetric, 2574136 symmetric, 2637415.

We diagram the symmetric solutions 4 to 7. An arrangement of queens in unguard on a torus board has the extra property that every broken diagonal also contains one queen. Such a pattern is called a pandiagonal satin. The 1-square and the 5-square and the first 7-square example above are the smallest examples.

Here are the twelve 8-square cases, in numerical form. 1: 15863724, 2: 16837425, 3: 24683175, 4: 25713864, 5: 25741863, 6: 26174835, 7: 26831475, 8: 27581463, 9: 28613574, 10: 35281746, 11: 35841726, 12: 36258174.
Below they are shown in diagram form, with the symmetric solution, 10, in yellow; this is also the only solution with no queen in the central 4 by 4 area. Some other distinguishing geometrical properties are: 4 and 10 have no queens on the principal diagonals, 3 and 9 have a line of four, 9 is the only solution with three queens in the central 4 by 4 area, 8 has an unevenly spaced line of three (b7-e1), 11 has no line of three, 5, 7 and 12 each have two lines of three (crossing at the centre of a parallelogram), 2 has no parallelograms. In no case do four queens form a square or rectangle. It was noticed by J. M. Andreas [reported in Rouse Ball (1956) p.170] that they all have an edge queen four cells from a corner.

On a grid board we can place 12 queens in unguard:

G(1) = 1. G(2) = 1. G(3) = 1. G(4) = 3: 1234, 1432, 2143. G(5) = 4: 12345, 14325, 15432, 21543.

G(6) = 7: 123456, 126543, 143265, 154326, 163452, 214365, 215634.

G(7) = 15: 1234567, 1265437, 1274563, 1634527, 1673452, 1734562, 1765432, 1674523, 2174563, 2176543, 2154376, 2651734, 3214765, 3217654, 3614725.

G(8) = 58:
2 rotary: 25836147, 28436517 and 2 birotary: 34872156, 43781265

24 axial: 12385674, 12745638, 12785634, 12845673, 14325876, 14328765, 14725836, 15432876, 16345287, 16385274, 16734528, 16785234, 17845623, 18365472, 18765432, 21845673, 21876543, 23416785, 25476183, 27416385, 32187654, 36187254, 37614825, 43618725

12 biaxial: 12345678, 12654378, 16745238, 17345628, 17654328, 21436587, 21563487, 32154876, 34127856, 37154826, 43218765, 47618325

18 asymmetric: 12784563, 14365872, 14762385, 14765823, 14765832, 15482673, 16348725, 18456732, 21476583, 23761845, 23816745, 23856714, 25437816, 25871436, 25876143, 27815436, 27816345, 34167825

I use the term composite to indicate a compound of pieces of different types, in this case compounds of rider and leaper. Knighted pieces, having added power of knight, have long been popular in variant versions of chess.

5×: 2 axial: 12543, 14523.

6×: 14 consisting of 1 rotary: 236145; 6 axial: 123654, 125436, 125634, 165432, 216543, 361452; 2 biaxial: 145236, 321654; 5 asymmetric: 143652, 145623, 145632, 214563, 256143.

Dawson also gave the following problem (#303 in PFCS): Place 8 Knighted Rooks on a 7 by 7 board so that each 6 by 6 portion of it shows 6 Knighted Rooks with no guards. This may be done in three ways, with the four groups of (R + Kt)s fundamentally different. Here are the solutions (the black pieces are guarded):

If you start at any piece in a bisatin, then move to the other piece in the same rank, then to the other piece in the same file as the second, then to the other piece in the same rank as the third, and so on, you will eventually return to the first piece, having circuited all or some of the pieces. A bisatin is thus equivalent to a rook circuit, or a set of superimposed rook circuits, having one move in each rank and file. These diagrams show all the geometrically different bisatins of sizes 2, 3 and 4:

Denoting the number of bisatins of size n by B(n) we see that B(2) = 1, and B(3) = 6, since the first bisatin of size 3 can occur in two orientations and the second in four orientations.

Here there are 6 asymmetric each occurring in 8 orientations (white), 2 rotary and 6 axial each giving 4 orientations (blue),
4 biaxial occurring in 2 orientations (red), and 2 octonary having 1 orientation (yellow), thus
B(4) = 2×1 + 4×2 + 8×4 + 6×8 = 90.

In the special case of 4 by 4 bisatins each line contains two pieces and two vacant cells, so reversing the colouring produces a complementary bisatin. The first four columns in the chart above show the four pairs of complements; the other twelve are self-complementary.

The alternate marks in a bisatin of one circuit form two satins. Every bisatin can be expressed as a combination of two satins, uniquely when there is just one circuit, and in 2^(m–1) ways when there are m circuits, since after the first circuit has been split into two parts A and B, the two parts of each subsequent circuit can be assigned to either A or B.

Theorem: There are (n!)^2/(2n) bisatins of one circuit of size n by n. Or, in terms of a recurrence relation, which may be more convenient to calculate:

A(n) = n(n–1)A(n–1) with A(2) = 1.

Proof: Choose the positions of pieces 1 and 2 in the top rank: there are n(n–1)/2 choices. Piece 3 may now be in any of n–1 cells, and for piece 4 there are n–2 choices. Piece 5 may then be in any of n–2 cells, and so on. Thus the total of choices is given by the product: ½n(n–1).(n–1)(n–2)^2.(n–3)^2...2^2.1^2 which equals (n!^2)/2n.

Theorem: A recurrence relaton for the total number B(n) of bisatins of all types of size n is as follows:

B(n) = n(n–1)B(n–1) + ½n(n–1)^2.B(n–2) with B(2) = 1 and B(3) = 6.

Proof: (1) The cases B(2) and B(3) are illustrated above. For a bisatin of side n we can always start as for the enumeration of bisatins of one circuit, identifying pieces 1, 2 and 3; but now there are two cases. The cell in the same file as piece 1 and the same rank as piece 3 is either occupied or vacant. In the occupied case the marks 1,2,3,4 form a circuit. Deletion of the ranks and files in which this circuit lies gives a bisatin of side n–2. In the vacant case we can delete the top rank (containing pieces 1 and 2) and the file containing pieces 2 and 3, and insert a new piece in the vacant space in the file containing piece 1 and the rank containing piece 3, thus leaving a bisatin of side n–1. By this process any bisatin can be reduced to a unique bisatin of smaller size. (2) Reversing the process we can form from a bisatin of size n–2 a total of ½n(n–1)^2 bisatins of size n by addition of a circuit of four pieces, two in the new top rank: there being n– choices for the position of the other extra rank and ½n(n–1) ways to place the two new files in relation to the existing files. This gives the second term in the recurrence. (3) The other term arises from expanding a bisatin of size n–1 to size n by choosing one of its pieces to be deleted, 2(n–1) choices, and inserting an extra rank at the top and an extra file, n possible positions, to left or right of the chosen piece, giving 2n(n–1) choices in all: but we must divide by 2 since the extra file has to be to the right. (The number of right and left cases must be the same overall, though not in individual cases.)

The following figures were calculated using the above recurrences.

n	2	3	4	5	6	7	8
B(n)	1	6	90	2040	67950	3110940	187530840
A(n)	1	6	72	1440	43200	1814400	101606400
C(n)	0	0	18	600	24750	1296540	85924440

The last line is the difference of the previous two: C(n) = B(n) – A(n)
and counts the number of separable bisatins (i.e. of two or more circuits).

[In the following issue of Games and Puzzles Journal T. H. Willcocks recalled that H. H. Cross had solved the problem of B(n) around 1959 (in the Fairy Chess Correspondence Circle), expressing the result by a formula using a "hypergeometric series" F(a,b;z) = 1 + abz + a(a+1)(b(b+1)z^2/12 + ..., the solution being F(–n,½;2)n!/(–2)^n. Mr Willcocks evaluated this for n = 2, 3, 4 and 5 and found the results in agreement with those from my recurrence method.]

Greater Lion. This captures by a hop over one piece along any straight line of cells, not just lateral or diagonal. On the 8 by 8 board the maximum is still 16. For example: 68,14,68,24,57,12,35,37 (Sam Loyd, Puzzle Magazine January 1908) or: 58,46,26,17,23,17,35,48 (Filipiak?). These arrangements are usually presented as a queen-placing problem with no three queens in a straight line.

Grasshopper. This is like a Lion but can only reach the cell immediately beyond the hurdle. On the 8 by 8 board the maximum in unguard is 22, for example: 2468,1,468,12,468,12,358,1357.

Kangaroo. This is like a Lion but hops over two pieces. On the 8 by 8 board the maximum in unguard is 24, with three in each rank and file. For example: 348,246,478,123,678,125,357,156 (G. P. Jelliss, 4 February 1985). This is symmetric and has four lines of four a8-d2, a8-g5, b4-h1, e7-h1.

Greater Kangaroo. Like a Kangaroo but acting along any lines. On the 8 by 8 board the maximum in unguard is still 24, for example: 278,137,245,146,128,468,357,356 (G. P. Jelliss, 4 February 1985). This is asymmetric.

Triple-Jumper. Like a Lion but hops over three pieces. On the 8 by 8 board the maximum in unguard is 32, with four in each rank and file. For example: 5678,2358,2358,5678,1234,1467,1467,1234 (G. P. Jelliss).

Greater Lion

Kangaroo

Greater Kangaroo

Triple Jumper