The Games and Puzzles Journal — Issue 34, Appendix |
This appendix gives some additional diagrams of solutions, in some cases where the full number of solutions on small boards is quite large.
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, one of which is not chequering, T = 2), for 4×4 and 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), chequering on 6×6 or larger.
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), chequering on 8×8 or larger.
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), chequering on 8×8 or larger.
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 with both coordinates odd, in which case they are confined to cells of one colour on the chequered board, and which are able, on a sufficiently large board, to get from any cell to any other cell of the same colour.
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 consists of leapers whose coordinates have a common factor k in which case they are restricted to k^2 separate domains (or 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.
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, a1, 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 red 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. As for giraffe, plus the fifth antelope solution.
There are obviously many other cases to examine.