ç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 37, January-February 2005

Chess-Piece Arrangement Problems

by George Jelliss

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


Sections on this page: — IntroductionRiders (e.g. Rook) — Compound Riders (e.g. Queen) — Composite Riders (e.g. Rook + Knight) — Hoppers (e.g. Lion and Grasshopper) — End
Introduction é

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.


Riders é


Rook: {0,1}-rider. This piece moves along ranks or files to any distance. The problem of maximum rooks in unguard on a square board of side n is solved by n rooks, one in each rank and file. Such patterns are known as satin squares (a term from weaving).

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.

n123456789
T(n)12624120720504040320362880
G(n)112723115694528246066

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.


Bishop: {1,1}-rider. This piece moves along the diagonals. On the n by n board the maximum number of bishops in unguard is 2(n–1), except when n = 1, for example they can be placed on all cells of the first and last files, except for the two cells on the first rank. They can be arranged in T(n) = 2^n ways (n > 1).

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.


Nightrider: {1,2}-rider. This piece moves along straight lines of knight moves. Solutions for boards of sides 1, 2, 3, 4 are the same as for the knight (P = 1, 4, 5, 8; G = 1, 1, 2, 3; T = 1, 1, 2, 6) since the {2,4} double knight move requires a board of at least 5 ranks or files. Here are results for the next four board sizes: 5×5: P = 10 (e.g. abcde14, two rows of five); 6×6: P = 16 (e.g. abef1256, a 2 by 2 square in each corner); 7×7: P = 17 (e.g. ab1267, d4, fg1267, a 2 by 2 square in each corner and one in the centre); 8×8: P = 20 (e.g. 1368,27,1368,0,0,1368,27,1368, a quincunx in each corner).


Compound Riders é


Queen: Rook + Bishop. The unguard problem for the queens, one of the most famous of chessboard puzzles, is solved for n = 2 or 3 by n–1 queens, but on larger boards by n queens, one in each rank and file, with no two in line diagonally. This is a special type of satin, which may be called a reginal satin. The problem of the 8 queens in unguard on the normal chessboard was apparently first proposed by Max Bezzel in the Berliner Schachzeitung 1848, and first fully solved by Franz Nauck in Leipziger Illustrierte Zeitung 1850. Here are the numerical results for boards 1 to 9:

n123456789
T(n)14821044092352
G(n)11112161246

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:


Raven: Rook + Nightrider. This problem was analysed by T. R. Dawson in Comptes rendus de la Congres International de Recreations Mathematiques 1937 (edited by M. Kraitchik), p.49, where it was presented as a problem of arranging Rooks with no two in a line of knight moves. As with Rooks the maximum is n. The type with all men along one diagonal remains an unguard arrangement when circularly permuted, except in the cases when the side is a multiple of 3.

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


Composite Riders é

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.


Chancellor: Rook + Knight. (This piece, the Knighted Rook, is also known under many other names). This unguard problem was investigated for boards up to size 6 by T. R. Dawson in Problemist Fairy Chess Supplement December 1931. Any solution for the Raven (Rook + Nightrider) also solves this problem. The following are the extra solutions:

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):


Amazon: Queen + Knight. Maximum is 6 in unguard on the 8 by 8 board, e.g. a2c5d8e1g6h3, a2c5d1e8f4h7, a2b5c8d1e4g7.


Hoppers é


Pao or Rion: Rook-Lion. These capture by a hop over one man along rook lines. (They differ in their non-capture move: the Pao moving like a Rook, while the Rion moves in the same way that it captures). On the 8 by 8 board the maximum in unguard is 16, arranged in a bisatin, that is with two in each rank and file. For example: 18367254 plus 45276813 (a bisatin of two circuits).


In Games and Puzzles Journal issue 10 (1989) I gave the following general results on bisatins.

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.

n2345678
B(n)16902040679503110940187530840
A(n)16721440432001814400101606400
C(n)001860024750129654085924440

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.]


Leo or Lion. These are like Pao or Rion, but acting along diagonals as well. On the 8 by 8 board the maximum is still 16. For example: 46718235 plus 82436571 (K. Fabel, Schach und Zahl 1966) a symmetric bisatin of one circuit. This was presented as a problem of arranging Queens so that there are no more than two in each queen-line.

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


Back to: Arrangements