Theory of Journeys

© 2001 by George Jelliss, 4 January 2001

Sections on this page: — Theory of JourneysAngles, or Two-move JourneysThree-move and Longer JourneysPuzzle Solutions

«Theory of Journeys.

Any sequence of moves constitutes a journey. The resulting change in position of the moved man is always equivalent to a single leap; we thus speak of a (p,q)-journey if the final cell reached is a (p,q) move from the initial cell. A journey is either open (ending at a different cell from that where it started) or closed (ending at the initial cell). A closed jourey is a (0,0)-journey.

Reordering Principle: THEOREM: On a sufficiently large board a series of moves will reach the same destination, from a given initial cell, regardless of the order in which the moves are made.

Proof: Any move in the journey takes the piece a given distance horizontally and a given distance vertically (these distances may be positive, negative or zero). The sums of the horizontal and of the vertical moves give the coordinates of the end point relative to the start point. A sum of distances is independent of the order in which they are added.

Number of Journeys: Consider a (p,q) journey of j = a + b + c + d + a' + b' + c' + d' moves in the eight directions of an {r,s} skew-mover. The number of ways these moves can be reordered is, by well known algebra, elegantly expressed as j!/(a!b!c!...). For example, diagram (A) illustrates the 5!/2!2! = 30 knight journeys formed of two moves in the (1,2) direction, two in the (2,1) direction and one in the (2,–1) direction from a2 to i7, that is an (8,5)-journey of 5 moves. The same diagram also illustrates the 5! = 120 journeys formed of five moves, one in each of the directions (1,2), (2,1), (2,–1), (–1,–2), (–2,–1), from d5 to f4, but since two pairs of these moves are in opposite directions some of these journeys involve switchbacks and circuits.

The interesting patterns formed by the shortest journeys of a given leaper between two given cells were first pointed out to me by C.M.B.Tylor [Chessics vol.2 nr.19 p.30 1984]. Diagram (B) shows the 12 knight's paths of three moves between two adjacent cells, forming a pattern of two interlocking cubes. Diagram (C) shows the 24 knight's paths of four moves to make a (0,6) journey, forming a 'hypercube' pattern (the 4-dimensional equivalent of the cube).
Recreation: Try constructing all the shortest knight journeys between two arbitrarily chosen cells to see the pattern that appears. Draw four-move (0,10)-journeys by zebra and giraffe for comparison.

The Journey Equations: Adding horizontal and vertical components we get the journey equations:
(1a) p = [(a – a') + (d – d')]r + [(b – b') + (c – c')]s
(1b) q = [(a – a') + (d' – d)]s + [(b – b') + (c' – c)]r.
Substituting A = a – a', B = b – b', C = c – c', D = d – d' the journey equations take the simpler form:
(2a) p = (A + D)r + (B + C)s and (2b) q = (A – D)s + (B – C)r.
We will make much use of these equations subsequently.

Simplified Journeys: In a journey involving moves in opposite directions we can re-order the moves to bring the opposing moves together to cancel each other out. The journey of j moves is reduced by this method to a journey of i = |A| + |B| + |C| + |D| moves in four or fewer of the eight directions. A series of moves all in the same direction is a ride. Thus by reordering we reduce any journey to 4 or fewer rides in different lines.

The four rides can be taken in 4! = 24 different orders, forming a hyper-parallelogram pattern of the type illustrated below. The diagrams simplify considerably if fewer than 4 directions are used, becoming a parallelepiped (3! = 6) when three are used, parallelogram (2! = 2) when two are used, line (1! = 1) when only one is used, and point (0! = 1) when all 4 rides are zero.

Closed Journeys: In the case of a closed journey p = q = 0, so the journey equations reduce to:
0 = (A + D)r + (B + C)s and 0 = (A – D)s + (B – C)r,
from which, since s is not 0, we get
r/s = –(B + C)/(A + D) = –(A – D)/(B – C)
and multiplying through by –(A + D)(B –C) gives us
(B + C)(B – C) = (A + D)(A – D)
which is the same as B^2 – C^2 = A^2 – D^2.
We can now substitute the absolute values since the squares of negative numbers are positive, and so finally
|A|^2 + |C|^2 = |B|^2 + |D|^2.

Geometrically this relation means that the four rides (when none is zero) form two right angled triangles with a common longest side, A being perpendicular to C and B to D. This is obviously possible whenever A = B and C = D or when A = D and B = C in which cases the quadrilateral is a kite when arranged so that no two lines cross, or a bow-tie when they cross. But there are also skew cases such as (A,C) = (5,5), (B,D) = (1,7). The cases with perimeters up to 30 units are: 7,1;5,5 (18); 8,1;7,4 (20); 9,2;7,6 (24); 11,2;10,5 (28); 11,3;9,7 (30); 12,1;9,8 (30).

When one of the rides reduces to zero the three rides form a right-angled triangle. For an {r,s}-mover with r < s the sides of this triangle must be in the ratios s^2 – r^2 : 2rs : r^2 + s^2.
In the case of the knight we get the famous 3 : 4 : 5 triangle.

We can use the above results to provide an alternative proof of the following:
THEOREM: Any closed journey by an {r,s} skew leaper consists of an even number of moves.
Proof: For any journey we have i^2 = (|A| + |B| + |C| + |D|)^2 =
|A|^2 + |B|^2 + |C|^2 + |D|^2 + 2(|A||B| + |A||C| + |A||D| + |B||C| + |B||D| + |C||D|).
Therefore in the case of a circuit, since |A|^2 + |C|^2 = |B|^2 + |D|^2,
i^2 is even, and hence i also is even (since the square of an odd number would be odd). In other words we have proved that a circuit of an odd number of moves by a single-pattern leaper is impossible.

Compact Journeys: H.J.R.Murray (1942) considered the problem of arranging the moves in these simplified journeys (which, following Jaenisch (1862), he called 'irreducible chains') so as to pack them within the smallest possible board. The following are his results for the 2,2,1,1 and 3,3,1,1 and 5,4,3 cases, and my own best result for the 7,5,5,1 case.

Shown is a ride pattern for all possible ways of making a closed journey of type 7,1;5,5.

Puzzle 1: Fit the 8,1;7,4 case onto a smallest possible board.

«Angles, or Two-move Journeys.

Two-Move Journeys and Angles: Two-move journeys of a skew mover are of seven types when classified in terms of the equivalent {p,q} move or by the angle between the two lines. We will number the angles 0 to 6 so that, in the case of the knight, the number measures the angle to the nearest multiple of 30°. The angles can also be described as Null, Diagonal Acute, Lateral Acute, Right, Lateral Obtuse, Diagonal Obtuse and Straight.

There are always two choices for the right-angle move. When necessary we distinguish them as 3D and 3L (or just D and L) according to whether the second move crosses a diagonal or lateral from the starting point of the first move. The reverse journeys of 0, 1, 2, 4, 5, 6 have the same code, but each of the right-angle moves is the reverse of the other. Note that the distinction between 3D and 3L is not that between moves to right or left (clockwise or anticlockwise) either type can occur in either direction.

The two acute angles are a = 2 tan–1 [(s – r)/(s + r)] and b = 2 tan–1 (r/s), related by a + b = 90°. These angles can never be equal, since this would require r/s = (s – r)/(s + r) which implies (r + s)/s = Ö2, but the square root of two cannot be expressed as a ratio of whole numbers. The angle b is smallest if r/s < Ö2, but a is smallest if r/s > Ö2. The angles a and b are the acute angles of the right-angled triangle with sides in the proportions
(s^2 – r^2) : 2rs : (s^2 + r^2).
In the case of the knight this is the 3 : 4 : 5 triangle. Murray (1942) gives the values of these angles for the knight in degrees, minutes and seconds as follows: a = 36° 52' 11.4" and b = 53° 7' 48.6".
Puzzle 2: For which leaper on the 8×8 board are a and b most nearly equal?
Puzzle 3: What leapers other than {kr,ks} can make the same angles as {r,s}?

Angles in Closed Tours: Some general propositions concerning the numbers of the different angles in closed knight's tours were proved by Fred Schuh Wonderlijke Problemen (1943) [translated as The Master Book of Mathematical Recreations (1968)] and these are generalised here to closed journeys by free-leapers of all types. The number of angles of types 1, 3, 4, say, in a path is denoted by N(1, 3, 4).
(1) The total number of angles in a closed journey, including the angle where the last and first moves meet, is N(1, 2, 3, 4, 5, 6) = N(1) + N(2) + N(3) + N(4) + N(5) + N(6) which equals the total number of moves and is even, as we have proved earlier.
(2) The move pairs with angles 1, 3 and 5 move the leaper an odd number of ranks and files, since the numbers involved are s – r and s + r which are odd for free-leapers. It follows that N(1, 3, 5) is even in any closed journey (since the total number of ranks or files moved is even if the piece has to get back to its original rank and file — the same number out and back).
(3) Move-pairs with angles 2, 4 and 6 move the leaper an even number of ranks and files. From the previous two results we must have N(2, 4, 6) even also in a closed path.
(4) Move-pairs with angles 1, 2, 4 and 5 rotate the leaper's move by angles ±a, ±(90°–a), ±(90°+a) and ±(180°–a) clockwise or anticlockwise, and a and 90° are incommensurable (i.e. no whole number multiple of a is a whole number multiple of 90°). The total angle moved through must be a multiple of 360°, since the angle between the last and first moves reorientates the piece to face in the same direction as it started out. Therefore N(1, 2, 4, 5) is even in a closed path, because positive and negative alphas must balance out.
(5) Combining results (4) and (1) tells us that N(3, 6) is even.
(6) Saying 'the sum of two quantities is even' can alternatively be expressed by saying that 'two quantities are of the same parity', that is, if one is odd the other is odd, and if one is even the other is even. Thus the above results can be summarised by saying that in a closed path the numbers of right (3), straight (6), diagonal (1 or 5) and lateral (2 or 4) angles are always of the same parity. In a symmetric path they are obviously all even.

«Three-move and Longer Journeys.

Three-Move Journeys: Three-move journeys without switchbacks, considered directionally, are of 7×7 = 49 types, since at the second and third moves there is in each case a choice of 7 directions for the next move. We can indicate them by ordered pairs of the angle-codes for two-move journeys. There are 7 three-move paths that are of the same type when traversed in the opposite direction (11, 22, DL, LD, 44, 55, 66). There are 20 not using right angles that are of type uv reversing to vu (12/21, 14/41, 15/51, 16/61, 24/42, 25/52, 26/62, 45/54, 46/64, 56/65). Then there are 20 using one right angle, the reverse of uD being Lu and of uL being Du (u not D or L). There remain the pair of cases DD and LL, each the reverse of the other. The rule to code the reverse journey is: reverse the sequence and replace D by L and L by D.
Puzzle 4: Why are DL and LD of the same length but in different directions?

Geometrically there are 7(7+1)/2 = 28 different 3-move paths: 11, 12/21, 1D/L1, 1L/D1, 14/41, 15/51, 16/61, 22, 2D/L2, 2L/D2, 24/42, 25/52, 26/62, LL/DD, DL, LD, L4/4D, 4L/D4, L5/5D, 5L/D5, L6/6D, 6L/D6, 44, 45/54, 46/64, 55, 56/65, 66.

There are only 12 types of triple leap when classified in terms of equivalent {p,q} move: 11, 16, = {|2r–s|, |2s–r|}, 12, 1D, 2L = {r, |2r–s|}, 1L, 14, L4 = {s, |2s–r|}, 15, 24, DD = {r,s}, 22, 26 = {3r,s}, 2D, 25, D5 = {2r+s,r}, DL, L6 = {|2s–r|, 2r+s}, LD, D6 = {2s+r, |2r–s|}, 34, L5, 45 = {s,2s+r}, 44, 46 = {r,3s}, 55, 56 ={2r+s, 2s+r}, 66 = {3r,3s}.

For the particular cases of knight and camel the types of three-move journeys reduce to fewer. For the knight {1,2} we have {s, 3r} = {2, 3} = {r, 2s–r}. For the camel {1, 3} we have {s–2r, 2s–r} = {1, 5}= {r, 2r+s}.

These results provide another proof that a triangle of moves by an {r,s} skew leaper is impossible. Since neither r nor s is zero the only case where {p,q} might be {0,0} is where subtractions occur in both coordinates. The only case is {|2r–s|, |2s–r|} which requires 2r = s and 2s = r which implies r = s = 0.

Four-Move Journeys: We can combine two 2-move journeys to form a 4-move circuit in three ways; by angle codes: 1515, 2424, DDDD (which is the same as LLLL). In coding a closed path of 2k moves all 2k angles are stated, the cyclic sequence being broken to give the smallest multi-digit number. Note that in a convex circuit the angle codes must add to 6k (counting D and L as 3).

In terms of sequences of angle codes four-move journeys without switchbacks number 7^3 = 343. This count includes 6 entries for the three four-move circuits (151, 515; 242, 424; DDD, LLL) and 6 entries for three skew-symmetric paths, having an axis of symmetry in an {r,s} direction and formed of right angles and straights (DLD/LDL; D6D/L6L; 6D6/6L6). The remaining 331 codes represent 150 asymmetric and 31 symmetric open paths (2×150 + 31 = 331). These symmetric paths of course give the same code when traversed in either direction.

Six-Move Circuits: By combining two three-move paths between the same cells we can form six-move circuits. The following two diagrams (using Giraffe {1,4} leaps as an example) show the 13 different circuits that are always possible with any {r,s} skew leaper. The 'open book' pattern gives 9 cases (AA', AB, AB', AC, AC', BB', BC, BC', CC' or in angle codes: 12DD25, 1241DD, 15L42D, 1D42L5, 14LL45, 156156, 245LL5, 246246, DD6DD6) while the 'cube' pattern gives 4 cases (ABC, ABD, ACD, BCD, where for example ABD denotes the hexagon ABD'A'B'D'; in angle codes: 12D12D, 1D41D4, 25D25D, D54D54).

In the case of knight {1,2} and camel {1,3} however, there are 12 further circuits possible in addition to the above 13, making 25 in all. [A note in Fairy Chess Review (November 1949 p.68) states this total was reported "long ago in Chess Amateur", but I have not been able to trace the exact reference.]

The reason for the extra circuits being possible in the case of the knight is that certain of the three-move paths, namely 11, 12, 1D, 16, D2, LD, 36, in which the end-points are separated by |2r–s| ranks or files in the general case are in the case of the knight on the same rank or file, since for the knight 2r = s. Similarly in the case of the camel the end-points of the three-move paths 12, 1D, 22, D2, DL, L6, 26, lie on a diagonal. Any knight path can in fact be converted into a camel path by increasing all lengths by a factor of root 2 and rotating through 45 degrees. This correspondence between knight and camel was first pointed out by T.R.Dawson in the Problemist Fairy Chess Supplement, June 1933, and has been independently rediscovered by several other workers since. The following are the twelve extra circuits (in angle code: 112112, 121D2L, 122214. 141626, 222L4D, 2LD2LD, 26L4D6, 11261D, 122L1D, 1262L4, 1D62LD, 1D61D6):

The above results account to a considerable extent for the greater touring ability of the knight as compared to other leapers and single it out for special study.

Eight-Move Symmetric Circuits: The symmetric 8-move circuits were enumerated by T.R.Dawson, finding 106, and he illustrated 100 of them in his series of knights tours with square numbers in symmetric closed knight chains (these are all diagrammed in my booklet on Figured Tours). The following are the results of a check on this enumeraton using our angle-coding method. The enumeration is quite tricky, there being several special cases easily overlooked. In particular there are three showing skew symmetry, which we show first (1 with octonary symmetry, 1 with biaxial symmetry and 1 with a single axis). By joining together two equal symmetric four-move paths we can form 10 circuits with biaxial or higher symmetry (4 octonary, 3 with lateral axes and 3 with diagonal axes).

By joining together two different symmetric four-move paths we can, for the general {r,s} skew leaper, form 36 symmetric circuits with a single axis of symmetry. There are 18 with lateral and 18 with diagonal symmetry, occurring in modally related pairs (10 without self-intersection); that is lateral angles in one correspond to diagonal angles in the other. There are also four special cases of axial symmetry formed by reflecting an asymmetric four-move path in the perpendicular bisector of the line joining its end-points (2 with lateral and 2 with diagonal axis).

In the special cases of knight and camel we have to add a further 16 circuits formed by the first method, and 4 formed by the second method, all with diagonal axis for the knight but lateral axis for the camel. These connections are not possible in the general case since the end-points of the two component paths are at different distances apart in the first method, and are not in the same lateral or diagonal in the second method.

We now come to the cases with pure rotational symmetry. By joining an asymmetric four-move path of an {r,s} skew leaper with a 180° rotated copy of itself we can form a symmetric circuit with pure rotatory symmetry in 29 cases, as shown below, classified into 3 self-modal forms (3564, 1623, 1254) and 13 modally related pairs. The 29 can also be classified into 12 centred on the corner of a cell, and 17 on the centre of a cell. In the case of the knight 8 of the 29 circuits self-intersect, but this is not necessarily the case for other pieces: while the circuit 2356 is non-intersecting for the knight or zebra, its modal twin 1346 intersects, but for the giraffe, the first is intersecting and the second not.

It is very easy to miss four further circuits with pure rotational symmetry that are possible in the case of knight and camel. These have Bergholtian symmetry, in which the path crosses itself at the centre. These cannot be split into two equal four-move paths, but can be analysed into two equal three-move paths whose ends in the case of the knight are separated by {0,1} or {0,2} moves thus permitting them to be joined to the X of knight moves (in the case of the camel moves the ends of the X are separated by {1,1} and {2,2} moves). Alternatively they can be analysed into two three-move paths with rotary symmetry which cross at their mid-points and whose ends can be joined.

«Puzzle Solutions.

Puzzle 1: The following diagram shows how to fit the 8,1;7,4 case onto a smallest possible board.

Puzzle 2: For which leaper on the 8×8 board are a and b most nearly equal? Answer: the {2,5} leaper is slightly closer than the {3,7} leaper, since 2/5 = 0.4 and 3/7 = 0.428571. The first is out by 0.014214 and the second by 0.014357.
Puzzle 3: What leapers other than {kr,ks} can make the same angles as {r,s}? Answer the {s–r, s+r} leaper. This result is due to O. E. Vinje, (Fairy Chess Review December 1940, problem 4656). In particular the camel {1,3} has the same angles between its moves as the knight {1,2}.
Puzzle 4: Why are DL and LD of the same length but in different directions? Answer; the moves DL = {|2r–s|, 2s+r} and LD = {2r+s, 2s–r} are always different, because equality would entail either 2s+r = 2r+s or 2s+r = 2s–r, and these conditions imply r=s or r=0 respectively, contradicting the assumption that the leaper is skew. The fact that they are of the same length is obvious from geometrical congruence, but this can be confirmed by algebra as follows: (2s–r)^2 + (2r+s)^2 = 5s^2 + 5r^2 = (2r–s)^2 + (2s+r)^2. The length of the triple leap is root 5 times the length of the {r,s} move.

Back to top