© 2001 by George Jelliss, 4 January 2001
This section of Knights Tour Notes goes back to first principles and considers what pieces like the knight can be defined, and their properties of movement. We begin with some material on theory of moves and paths in general.
By a net we mean a collection of elements called cells (usually represented as small geometrical areas) some of which are linked to each other (these links being shown by lines, curved or straight, drawn from cell centre to cell centre) and which cannot be divided into two collections of cells with no cell in one linked to any cell in the other; in other words the net is connected. A net of one cell is a singleton. A net of two cells is a domino. A cell linked to one other cell is an end. Thus a domino has two ends. A cell linked to two other cells is a passage. The number of other cells to which a cell is linked is its degree of linkage. A theorem of Euler (expressed in our terminology) is that: the number of cells of odd degree in a net is even (To prove this note that each link connects two cells, so the sum of the degrees of all the cells is twice the number of links, an even number. Sums and differences of even numbers are even. For a sum of odd numbers to be even there must be an even number of them.)
A net in which each cell is linked to no more than two other cells is a path; either an open path with two ends (also called a chain), or a closed path with no ends (also called a circuit). In terms purely of links there are two types of net with three cells, an open or closed path. The property of a net of being connected means that given any two cells an open path can be found, using only the links of the net, with those cells as its ends. A path, open or closed, that visits every cell of the net is what we mean by a tour.
By a board we mean a net in which the links have specified lengths. Cells whose links are of the minimum length, which we can take to be the unit of length, are said to be adjacent (and are usually represented by the cells having a common edge). By a chessboard we mean a board in which the unit links form straight lines in two mutually perpendicular directions, which we call ranks, shown horizontally across the screen, and files, shown vertically down the screen. (It is also possible to consider boards in which the cells form a hexagonal lattice, hexboards, or a three-dimensional lattices spaceboards; we may add notes on these at a later date.)
The ranks and files of a chessboard need not all contain the same number of cells, nor form unbroken straight lines; the outline of the board may be non-rectangular and there may be holes in the board. Any such board however can be expanded to form a rectangular board by adding cells in the holes and round the edges, to form the minimal containing rectangle.
The cells on a chessboard can be specified by an ordered pair of numerical coordinates (x,y) that count the number of unit links from a given cell (0,0) in the minimal containing rectangle. The cell taken as (0,0) is usually the lower left corner cell, so that the coordinates are whole numbers. The use of coordinates to record positions and moves in chess goes back at least to the time of al Adli (c.840), although different sequences of letters were used to label the ranks and the files. To apply mathematical methods it is necessary to make both coordinates numerical.
By a move we mean the transfer of a token from a cell (x,y) to a cell (x',y'), and we represent the move in length and direction by the ordered pair of numbers (x'–x,y'–y) = (u,v), where u and v can be positive, negative or zero. By the pattern of a move (u,v) we mean the pair of non-negative numbers {r,s} where r = |u|, s = |v| or vice versa, and r < s. A move of pattern {r,s} takes a piece from (x,y) to any of the up to eight cells (x±r,y±s) and (x±s,y±r) that are available within the confines of the board.
We allow the possibility that the initial and final cells of the move may be the same in which case we have a null move {0,0}. A move that has one coordinate zero, i.e. of pattern {0,s} is termed orthogonal or rookwise, i.e. horizontal or vertical, along the ranks or files of the lattice. A move with both coordinates of equal magnitude, i.e. of pattern {r,r} is termed diagonal or bishopwise, i.e. when the cells are square, lines of cells at 45° to the horizontal and vertical. A move with both coordinates different and non-zero we call skew. For a skew move on a sufficiently large board all eight moves from a given cell will be distinct, making a wheel formation. If r<s then the four moves (±r, ±s) are termed vertical while (±s, ±r) are horizontal. For diagonal or lateral moves the number reduces to four.
By a (chess)man we mean a token of distinctive design that can be placed to occupy certain cells of a chessboard and whose design indicates the moves that it is permitted to make, subject to the limitations that may be provided by the edges of the board or the presence or absence of other tokens, or any other conditions applying. By a (chess)piece we mean a chessman whose powers are independent of time, position on the board, or orientation, thus if able to make a move (u,v) of pattern {r,s} from a cell (x,y) then it can make any of the moves (±r, ±s) or (±s, ±r) from (x,y) or any other cell, subject to the existence of the destination cell. Given any pattern or set of patterns of moves then a piece can be defined, able to make just those moves from whichever cell of the board it is on. A simple piece is one having only a single pattern of move {r,s}; more complicated pieces are compound.
The freedom (of movement) of a piece can be measured by the fraction of the board to which it has access. Conversely the multiplicity of a piece is the number of pieces of that type needed to patrol all the cells of the board. A piece that is able to reach any square of the board from any other square in a series of moves (a requirement for any piece that makes a tour of the whole board) is a free piece; one that can reach all squares of one colour, but not the other colour, may be termed half-free. The mobility of a piece on a given board is the average number of moves it can make when placed at random on the board. This can be calculated by totalling the moves available to it at all the cells of the board and dividing by the number of cells.
A piece that cannot be blocked by men on intermediate cells we call a leaper. The shortest simple leapers
have acquired colourful names, some of them dating from mediaeval times, as follows:
{0,0} = dummy,
{0,1} = wazir, {1,1} = fers,
{0,2} = dabbaba, {1,2} = knight, {2,2} = alfil,
{0,3} = threeleaper, {1,3} = camel, {2,3} = zebra, {3,3} = tripper,
{0,4} = fourleaper, {1,4} = giraffe, {2,4} = lancer, {3,4} = antelope,
{4,4} = commuter.
The dummy merely occupies a cell. It occurs in some versions of chess which apply the rule that a pawn moved to its final rank has to wait there until a captured piece is available for it to promote to. The name wazir comes from a piece that appeared in a variant of chess played on an enlarged board with numerous extra pieces that was popular at the court of Timur (about 1400). The same game also included the dabbaba, whose name signifies a movable siege-engine. Pieces with the single and double diagonal steps, the fers and alfil, existed in mediaeval chess, as described in the Early History section. Their names derive from the Persian 'farzin' meaning counsellor and 'pil' meaning elephant. A piece with the knight move has existed in all forms of chess, and has always been named for the horse or a horseman. The camel and giraffe (the latter with added power to move further after its leap) were pieces in Timur's Great Chess.
The freedom of an {r, s}-leaper, on a 2s×2s board is 1/(k^2) or 1/2(k^2) according as (r + s)/k is odd or even, where k = hcf (r,s), the 'highest common factor' of r and s [G. P. Jelliss, Chessics, #2 1976 p.2 and #24 1985 p.94]. Thus for a simple leaper to be free on the 2s×2s or any larger board we must have hcf(r,s) = 1 and r + s odd. For a simple leaper to be half-free (that is with access to half the squares of the board; the white or black squares if the board is chequered) we must have hcf(r,s) = 1 and r + s even. If hcf(r,s) = k then the {r,s} leaper is confined to squares with coordinates (x±uk, y±vk) relative to its initial square (x,y) and cannot, for example, get to those squares (x±a, y±b) with a and b between 0 and k. If (r+s)/k is even the piece is confined to those squares (x±uk, y±vk) with u+v even, which is half of them.
The five named free simple leapers capable of moves on the 8×8 board are the wazir {0,1}, knight {1,2}, zebra {2,3}, giraffe {1,4} and antelope {3,4}, after which the series goes: {2,5}, {4,5}, {1,6}, {5,6}, {2,7}, {4,7}, {6,7}, {1,8}, {3,8}, {5,8}, {7,8}, {2,9}, {4,9}, {8,9}. All leapers of the families {z,z+1}, {1,2z} and {2,2z+1} are free. The half-free simple leapers are: fers {1,1}, camel {1,3} and: {1,5}, {3,5}, {1,7}, {3,7}, {5,7}, {1,9, {5,9}, {7,9}.... All leapers {1,2z+1} are half-free. Other leapers with coordinates up to 9 are: (a) with odd multiplicity; 9: {0,3}, {3,6}, {6,9}; 25: {0,5}; 49 {0,7}; 81 {0,9}; these, like free leapers always move to squares of a different colour: (b) with even multiplicity; 4: {0,2}, {2,4}, {4,6}, {2,8}, {6,8}; 8: {2,2}, {2,6}; 16: {0,4}, {4,8}; 18: {3,3}, {3,9}; 32: {4,4}; 36: {0,6}; 50: {5,5}; 64: {0,8}; 72: {6,6}; 98: {7,7}, 128: {8,8}, 162: {9,9}; these are all on squares of one colour.
The number of moves available to a simple skew leaper reaches its maximum value of eight only in the central regions of a sufficiently large board. THEOREM: For an {r,s} skew leaper on a square board n×n the mobility is 8(n–r)(n–s)/(n^2) and on a rectangular board m×n the mobility is [4(m–r)(n–s) + 4(m–s)(n–r)]/mn. Proof: On the square board we consider all its moves in one of the eight directions. The destinations of these moves must lie within a rectangle of (n–r)×(n–s) cells. Similarly on the rectangular board moves in the four horizontal directions lead to one rectangle, and moves in the 4 vertical directions to another rectangle. For lateral and diagonal leapers the mobilities are half the above values.
This result was given, in slightly different form, by Edouard Lucas in his Recreations Mathematiques (vol.IV, 1894, p.130).]
The board may be divided into regions according to the number of moves available to the leaper on cells in those regions. Each of these mobility patterns can be seen as a pattern of intersections of the eight rectangles described in the above theorem. The number of moves at a cell is the number of these rectangles in which the cell is contained. For lateral {0,s} or diagonal {s,s} simple leapers on a square board n×n only four mobility patterns can occur in each case, according as (a) n < s, (b) s < n < 2s, (c) n = 2s, (d) n > 2s, as illustrated below. Case (b) does not occur when s = 1.
In the case of {r,s} skew leapers, r < s, eight different mobility patterns can occur on square
boards according to the size of the board n×n and the relative proportions of the numbers r, s and n.
The case (b) s < n < 2s divides into five separate cases according to the value of r: (b1) s < n < 2r,
(b2) n = 2r, (b3) 2r < n < r + s, (b4) n = r + s, (b5) r + s < n < 2s.
Cases (a), (b4), (c), (d) occur for all skew leapers. The other four cases only occur under special conditions:
(b1) s < 2r – 1, (b2) s < 2r, (b3) r + 1 < s < 2r, (b5) r + 1 < s.
The mobility pattern of an {r,s} skew leaper on a square board of edge r+s has two moves available at every
cell except the central ones, this means the moves must form closed circuits. The {1,2k}-movers form a single
circuit. [I first gave the above results on mobility patterns in Chessics #24, 1985, p.88.]
Puzzle 1: What is the smallest board on which an {r,s} leaper can move from every cell?
Puzzle 2: On what board does the mobility of a {0,s} leaper equal 3?
Puzzle 3: Which is the smallest simple skew leaper that exhibits all eight mobility patterns?
Puzzle 4: On what size of board do the moves of an {r,s} leaper form circuits?
Puzzle 5: Which simple leapers on boards answering puzzle 4 form a single circuit?
A compound leaper is a piece that can make two or more different, non-null, patterns of leap.
The simplest and best known of course is the king. Names for all combinations using coordinates less than 3 are:
{0,1} + {1,1} = king,
{0,1}+{0,2} = wazaba, {1,1}+{0,2} = diamond,
{0,1}+(1,2} = emperor, {1,1}+{1,2} = prince, {0,2}+{1,2} = templar,
{0,1}+{2,2} = caliph, {1,1}+{2,2} = ferfil, {0,2}+{2,2} = alibaba, {1,2}+{2,2} = hospitaler.
Some other combinations named by chess problemists are:
{0,2}+{1,2}+{2,2} = squirrel, {1,2}+{1,3} = gnu, {1,3}+{2,3} = bison.
An important group of longer-leaping compounds are the fixed-distance leapers. As longer leaps are
considered cases arise in which different patterns of move have the same length.
The first such cases, and the only ones that can move on the 8×8 board, are the
{0,5}+{3,4} = fiveleaper, and the {5,5}+{1,7} = root-fifty-leaper.
T. R. Dawson gave an analysis of multi-pattern fixed-distance leapers on larger boards in
Chess Amateur August 1925:
Double-pattern: {4,7}+{1,8} = root-65L, {6,7}+{2,9} = root-85L, {6,8}+{0,10} = 10L,
{5,10}+{2,11} = root-125L, {7,9}+{3,11} = root-130L, {8,9}+{1,12} = root-145L,
{5,12}+{0,13} = 13L, {7,11}+{1,13} = root-170L, {8,11}+{4,13} = root-185L,
{10,10}+{2,14} = double-root-50L, {6,13}+{3,14} = root-205L, {10,11}+{5,14} = root221L,
{9,12}+{0,15} = 15L, {9,13}+{5,15} = root-250L, {8,14}+{2,16} = double-root-65L,
{11,12}+{3,16} = root-265L, {8,15}+{0,17} = 17L, {11,13}+{1,17} = root-290L,
{7,16}+{4,17} = root-305L.
Triple-pattern: {10,15}+{6,17}+{1,16} = root-325L, {15,20}+{7,24}+{0,25} = 25L
Quadruple-pattern: {23,24}+{12,31}+{9,32}+{4,33} = root-1105L
Quintuple-pattern: {39,52}+{33,56}+{25,60}+{16,63}+{0,65} = 65L.
Any combination of a piece with a free piece is obviously also free. It can however happen that a compound leaper is free even though none of its components, nor combinations of them, are free. A combination that has greater freedom than any of its components I have termed an amphibian [Chessics #24 1985 p.95], since it is able to move in two or more distinct realms. I think it is true to say that a combination of leapers with freedoms 1/a and 1/b produces a leaper with freedom 1/hcf(a,b). Thus for an amphibian a and b must have a common factor not equal to a or b; and for a free amphibian we must have hcf(a,b) = 1. The earliest example of a puzzle using an amphibian that I came across was one given by A. C. Pearson in The Twentieth Century Standard Puzzle Book 1907 (p.62 of Part 3). It uses a {1,1} + {0,3} = frog on a 5×5 board. The next three smallest amphibians combine the {0,3} with {0,2}, {2,2} and {1,3}. An alternating tour with any of these leapers is impossible on the 8×8; Proof: If at a8 we take a8-d8, then we must take g8-g5, then g2-d2, then a2-a5. No route from d5 is then free. The following are tours of the smallest possible boards by the four smallest amphibians.
|
|
|
|