| The Games and Puzzles Journal — Issue 34, July-August 2004 |
| (76) — Introduction | é |
As the title indicates, this issue is the first of several devoted to new and collected results on chess-piece arrangement problems. Many problems using one type of piece are more of a mathematical than a chess nature, whereas problems with multiple types of piece, which we will study in later Parts, begin to approach the domain of true chess problems. In order to fit in more data we show most small-board diagrams with small squares. In these a vacant cell is shown grey, and unguarded pieces are shown by white sqares, guarded pieces by black squares instead of by chess symbols. Only the most interesting patterns, particularly those showing symmetry, have been diagrammed, however some further results will be found in the Appendix.
There are two principal types of problems: Unguards and Coverings. Roughly speaking, in unguards we place the maximum number of pieces so none guards any other, whereas in coverings we place the minimum number of pieces so that all cells are guarded. A normal chess piece has a given mode of movement and captures in the same way, that is it moves to the cell occupied by its victim which is then removed from the board. This is in contrast to special pieces that have different move and capture (for instance pawns). A cell is said to be guarded by a given piece if that piece could capture on that cell were it occupied by an opposing piece. The simplest pieces, leapers and composite leapers, are considered first, in order of increasing move coordinates, in later Parts the simplest riders and their compounds with leapers and with other riders, and finally hoppers and more complex pieces are considered.
We confine our attention mainly to problems using square boards, although we will see that solving problems on larger square boards sometimes requires knowledge of the numbers of arrangements possible on smaller rectangular boards. So future developments should aim to include results on rectangular boards. The first task is simply to find a solution fitting the conditions, this is often difficult enough, however there is then the supplementary question of enumerating all possible solutions. For a board of side n we denote by P(n) the number of pieces of the given type that solve the problem, by T(n) the number of different solutions, and by G(n) the number of geometrically distinct solutions, not regarding rotations and reflections as different. Chequering of the board in these problems serves only to help visualise the diagonals and is usually ignored in counting the arrangements. On the 1×1 board of course P = G = T = 1 for all pieces. Where G = 1 and T = 1 we give only the value for P.
I use the following terms to describe the various types of symmetry possible in square patterns: asymmetric = occurring in 8 forms by rotation and reflection, axial = having one axis of symmetry (which may be lateral or diagonal) and thus 4 forms, biaxial = having two axes of symmetry (both lateral or both diagonal), and thus 2 forms, rotary = invariant to 180° rotation (but not to any other rotation), so having 4 forms, birotary = invariant to 90° rotation, thus having 2 forms, octonary = invariant to all rotations and reflections, having only 1 form.
| (77) — Free Leapers | é |
An {r,s}-leaper is said to be free on a given board if it is able to get from one cell to any other in a series of leaps. It follows that r and s must have no common factor, and further one must be even and the other odd, and finally (on a square board) they must be < half the side-length of the board. For all leapers of this type on a sufficiently large board the unguard task is solved by chequering. However, more pieces, or extra solutions with the same number of pieces, become possible if the board side is less than or equal to twice the longer move-coordinate of the leaper. Several cases where non-chequered solutions are possible on boards twice the longer move coordinate have been pointed out by Tom Marlow, 7 September 2004, and are now included below.
Wazir: {0,1} mover. This is the simplest case. To place maximum wazirs in unguard on any board we simply chequer the board and put them all on the same colour cells: in the case of an odd board (square or rectangle) the maximum is achieved by using those cells of the same colour as the corner cells, but on an even board either colour will do. The maximum number of wazirs that can be placed in unguard in these cases is therefore (n^2)/2 when n is even and (n^2 + 1)/2 when n is odd. On a rectangle m by n the number is mn/2 or (mn + 1)/2 according as mn is even or odd. Thus on any board G = 1. We show chequerings on all rectangular boards up to 5×5. Note that when both sides are odd (shown red) T = 1, but when one or both sides are even T = 2. This is the basis for calculating the totals T for many of the longer leapers.
For the longer {r,s} free leapers with r < s we consider arrangements on boards with side < 2s:
Knight: {1,2} leaper. 2×2 (P = 4), 3×3 (P = 5, G = 2, T = 2), 4×4 (P = 8, G = 3, T = 6, the two non-chequered solutions were spotted by T. W. Marlow). For larger boards chequering is the only way.
Zebra: {2,3} leaper. 2×2 (P = 4), 3×3 (P = 9), 4×4 (P = 12), 5×5 (P = 13, G = 4, T = 4), 6×6 (P = 20, G = 1, T = 2, special case found by T. W. Marlow). Chequering on larger boards.
Giraffe: {1,4} leaper. 2×2 (P = 4), 3×3 (P = 9), 4×4 (P = 16), 5×5 (P = 17, G = 2, T = 2), 6×6 (P = 20, G = 1, biaxial, T = 2), 7×7 (P = 25, G = 2, T = 2, chequered solution not shown), 8×8 (P = 32, G = 2, T = 4, chequered solution not shown, non-chequered solution found by T. W. Marlow). Chequering is the only solution on larger boards.
Antelope: {3,4} leaper. 2×2 (P = 4), 3×3 (P = 9), 4×4 (P = 16), 5×5 (P = 21), 6×6 (P = 24), 7×7 (P = 25, G = 8, two the same as for the giraffe, T = 8), 8×8 (P = 36, G = 1, T = 2, special case found by T. W. Marlow). Chequering on larger boards.
The same principle of solution will work for any pieces that guard or attack only dark squares when standing on light squares, or vice versa, and which also satisfy the freedom condition. For instance the panda which moves like a rook but only to squares of opposite shade.
| (78) — Half-Free Leapers | é |
This class consists of leapers able, from any cell, to access half the cells on any sufficiently large board. This means that (a) both coordinates must be odd, so that they are confined to cells of one colour on the chequered board, and (b) as for free leapers their move-coordinates, r and s, must have no common factor.
Fers: {1,1}-mover. 2×2 (P = 2, G = 1, T = 4), 3×3 (P = 6, G = 1, T = 2), 4×4 (P = 8, G = 7, 1 biaxial, 1 birotary, 2 axial, 3 asymmetric, T = 36), 5×5 (P = 15, G = 1, T = 2), 6×6 (P = 18, G = 46, of which 10 are symmetric, all axial, T = 328?), 7×7 (P = 28, G = 1, T = 2), 8×8 (P = 32, G = 477?, of which 41 are symmetrical; 32 axial, 3 rotary, 3 biaxial, 3 birotary, T = 3640?).
2×2, 3×3, 4×4 (7 cases) and 5×5
6×6 the 10 symmetric solutions
7×7 and 8×8 the 3 biaxial and 3 birotary solutions
Camel: {1,3} leaper. Like the wazir this piece has just one geometrically distinct solution on any square board. On all boards of side 5 or more this is a pattern of alternating stripes. 2×2 (P = 4), 3×3 (P = 9), 4×4 (P = 10, G = 1, T = 4), 5×5 (P = 15, G = 1, T = 2), 6×6 (P = 18, G = 1, T = 4), 7×7 (P = 28, G = 1, T = 2), 8×8 (P = 32, G = 1, T = 4).
| (79) — Bound Leapers | é |
This class (which might be called bounders instead of leapers!) consists of leapers whose coordinates have a common factor k > 1, in which case they are restricted to k^2 separate domains (when r + s is odd) or 2(k^2) separate domains (when r + s is even) — though possibly less on smaller boards.
Dabbaba: {0,2} leaper. On a large board a dabbaba has access to a quarter of the board, consisting of the cells with coordinates (odd,odd), (odd,even), (even,odd) or (even,even). To place the maximum dabbabas in unguard on each of these quarters is equivalent to the problem of placing wazirs on the board formed by closing up the spaces between the cells, i.e. they have to be arranged alternately, in chequered fashion. When these four chequerings are combined they result in patterns of two types, either a chequering of alternate 2×2 blocks of cells or alternate stripes two diagonals wide. We show the 8×8 solutions as typical (each is made up of four 4×4 solutions). 2×2 (P = 4), 3×3 (P = 5, G = 2, T = 8), 4×4 (P = 8, G = 6, T = 16), 5×5 (P = 13, G = 2, T = 8), 6×6 (P = 20, five 2×2 blocks in quincunx is the only solution), 7×7 (P = 25, G = 2, T = 8), 8×8 (P = 32, G = 6 ways, T = 16).
Threeleaper: {0,3} leaper. 2×2 (P = 4), 3×3 (P = 9), 4×4 (P = 10, G = 7, T = 32), 5×5 (P = 13, G = 51, T = 256 = 2^8), 6×6 (P = 18, G = 84, T = 512 = 2^9), 7×7 (P = 25, G = 51, T = 256), 8×8 (P = 34, G = 7, T = 32), 9×9 (P = 45, quincunx of five 3×3 blocks is the only solution). The squares of sides 10 to 15, 16 to 21, 22 to 27 and so on have the same numbers of solutions as for the cases 4 to 9. We show here only the most symmetric solutions, for others see the Appendix.
4×4: 7 cases
5×5: the 4 octonary and 4 biaxial cases (there are 25 other symmetric and 18 asymmetric cases)
6×6: the eight biaxial cases (there are 28 other symmetric and 48 asymmetric cases)
7×7: the 4 octonary and 4 biaxial cases (there are 25 other symmetric and 18 asymmetric cases)
8×8: 7 cases (the middle 4×4 patterns coincide with the 4×4 solutions).
9×9: 1 case
Fourleaper: {0,4} leaper. 2×2 (P = 4), 3×3 (P = 9), 4×4 (P = 16), 5×5 (P = 17, G = 20, 8 axial (shown) and 12 asymmetric, T = 8×4 + 12×8 = 2^7 = 128).
Other values I have worked out are: 6×6 (P = 20, T = 2^12 = 4096), 7×7 (P = 25, T = 2^15 = 32768).
Alfil: {2,2} leaper. 2×2 (P = 4), 3×3 (P = 7, G = 1, T = 4), 4×4 (P = 8, G = 39, T = 256) only the four with maximum symmetry are shown below (for the rest see the Appendix), 5×5 (P = 16, G = 2, T = 8), 6×6 (P = 16, G = 4, T = 16), 7×7 (P = 30, G = 2, T = 8), 8×8 (P = 32, G = 39?, T = 256), 9×9 (P = 37, G = 2, T = 8), 10×10 (P = 36, G = 4, T = 16).
| (80) — Compound Leapers | é |
King: {0,1} + {1,1} mover. The number of kings required is k^2 on square boards of side 2k or (2k – 1). There is always just one solution that has octonary symmetry, and in the case of odd-sided boards this is the only solution (with the kings on the cells with both coordinates odd, i.e. a135-c135-e135-...). For the even sided boards solutions are easily found, since each 2×2 block must contain one king, it is just a matter of ensuring no two are on adjacent cells, laterally or diagonally. Enumerating the solutions accurately is the difficult question. There is an account of a method of enumeration, giving totals on all boards up to 8×8, and also on rectangular boards up to 20×8 in K. Fabel, Schach und Zahl, 1966 (with contributions by C. E. Kemp and C. Bandelow) but the explanation is not clear to me. I have however checked the totals for 4×4 and 6×6 and the symmetric solutions 8×8 by another method. This method depends upon observing that in each row or column of 2×2 blocks there is always one break: in a row the kings to the left of the break stay in the left half of their block and the kings to the right stay in the right half (and similarly in the columns). The break can be at the left or right end of the row or between two blocks. Thus on the 2r×2s board with r rows and s columns of blocks, there are (s+1) ways of placing each of the r row breaks and (r+1) ways of placing each of the s column breaks, and therefore (r+1)^s × (s+1)^r ways of combining them. On a square board r×r this becomes (r+1)^(2r). That is the easy part. The problem now is to eliminate certain special cases which have kings diagonally adjacent.
The solutions are enumerated as follows:
2×2 (P = 1, G = 1, T = 4).
3×3 (P = 4, kings in the corner cells is the only solution).
4×4 (P = 4, G = 14, T = 79). In the case of the 4×4 board there is only one geometrically distinct case to be eliminated (shown in black below), and it occurs in two orientations, so the total of solutions is T = 3^4 – 2 = 81 – 2 = 79.
5×5 (P = 9, one solution).
6×6 (P = 9, G = 457, T = 4×14 + 8×443 = 3600). The formula above gives the crude figure of 4^6 = 4096. There are six geometrically distinct ways of arranging the breaks to force a pair of diagonally adjacent kings (two breaks in adjacent rows and two in adjacent files, with the two pairs of rows and files crossing). Four of these are axial and two are asymmetric, giving 32 oriented solutions. In each of these the two other breaks can be placed in 4 ways. So the total to be deducted is 32×(4^2) = 512. However, there are some cases where two of the illegal arrangements of breaks can be combined, and we have counted these twice and subtracted them, so they have to be added back in. They amount to 16 (two axial one asymmetric) and we at last arrive at the correct total: T = 4096 – 512 + 16 = 3600. Since the central 2×2 contains one king the only symmetry possible is with a single diagonal axis, there are 14 cases as illustrated, the 443 others are all asymmetric.
7×7 (P = 16, one solution).
8×8 (P = 16, G = 35312, T = 281571). The total for G here is derived from that for T, given by Fabel, together with my own (unchecked) enumeration of the symmetric cases as follows: 1 octonary, 1 biaxial, 10 birotary (these twelve cases are diagrammed below), 12 lateral axis, 121 diagonal axis, 80 rotary, from which I deduce 35087 asymmetric. Thus T = 1×1 + 2×(1 + 10) + 4×(12 + 121 + 80) + 8×35087 = 281571.
Alibaba: {0,2} + {2,2} leaper.
2×2 (P=4).
3×3 (P=4, G=3. T=16): 2 axial and 1 asymmetric.
4×4 (P=4, G=43, T=256). The four alibaba domains are 2×2 arrays, on each of which one alibaba can be placed in 4 ways hence T = 4^4.
The 43 geometrically different forms consist of 2 octonary, 2 biaxial, 1 birotary, 12 axial, 2 rotary, 24 asymmetric (1×2 + 2×3 + 4×14 + 8×24 = 256). We show the first five here, and the full set in the Appendix.
5×5 (P=9, G=10, T=64). The four alibaba domains consist of arrays 2×2, 2×3, 3×2 and 3×3. On these the king has 4, 4, 4 and 1 solutions, hence T = 4^3. We show the 10 geometrically distinct solutions, four axial 6 asymmetric, all oriented with b4 black.
6×6 (P=16, the alibabas form 2×2 squares in the corners of the board).
7×7 (P=16, T=6399). The four alibaba domains consist of arrays 3×3, 3×4, 4×3 and 4×4. On these the king has 1, 9, 9, and 79 solutions, so T = 1×9×9×79. We show the 1 octonary, 1 biaxial and 4 birotary solutions.
8×8 (P=16, T = 79^4 = 38950081). Each of the four domains accessible to the alibabas is a 4×4 array, so the problem is equivalent to four arrangements of kings on a 4×4 board, which has 79 solutions. We show the 7 octonary arrangements.
9×9 (P=25, T=79(X^2) where X is the number of king solutions on the 4×5 board, not yet determined).
Fiveleaper: {0,5} + {3,4} mover. 7×7: as for giraffe, plus the fifth antelope solution.
There are obviously many other cases to examine.
| Update: The Introduction and the colour scheme for the diagrams have been edited (June 2005) to conform to the scheme used in later Parts. The rest of the text is unaltered. |