© by George Jelliss, 4 January 2001, revised 7 March 2011
The general problem is: How few moves are needed for an {r,s}-mover to make a {p,q}-journey? In answering this problem we assume, for now, that the board edges are far enough away so as not to get in the way of any route we may try. Later, the problem of fitting the path onto the smallest possible board will be considered. If a smaller board than the minimum is specified then either the number of moves necessary will increase or the journey will become impossible.
For the wazir {0,1} the answer is easy: i = p+q, with p moves in one direction and q in the perpendicular direction. Shown are the (p+q)!/p!q! = 10 routes of a wazir to make a {2,3} journey of fewest moves, p+q = 5. The more general {0,s}-mover requires i = (p+q)/s moves.
For the fers {1,1} we must have p+q even, since it is confined to squares of one colour. Thus, assuming p £ q the minimum number of moves required is i = q, composed of (q–p)/2 in one direction and p + (q–p)/2 = (p+q)/2 at right angles. Illustrated are the q!/[(p+q)/2]![(q–p)/2]! = 4 routes of a fers in making a {2,4} journey. The more general {r,r}-mover requires i = q/r moves.
This leaves us with the more general case of skew movers. Any {p,q} journey by an {r,s} mover is geometrically similar to (that is a magnified version of) a {p/k, q/k} journey by an {r/k, s/k} mover, where k = hcf (r,s). (The journey equations show that any factor or r and s is also a factor of p and q.) We are thus left with the case hcf (r,s) = 1 to solve. The knight is a special case of this.
The problem for this case was considered by Jaenisch and by Murray (1942) who notes: "Any two points on the lattice can always be connected by a standard chain containing three vectors at most, in two ways: mA + nC ± Y and pB + qD ± Z, where m, n, p and q may have any integral values positive or negative, or be zero, and Y is either B or D and Z is either A or C. Consider the position of a point of the lattice with respect to the network of parallels to OA and OC [in the figure below]. Every point lies either on a corner of the squares formed by the intersections of paralels to OA and OC, or within one of these squares. There are four points inside every square, and each of these points links with a corner of the square by a vector which is one of B, B', D and D'. Thus, a chain O to P is 2A + C + D', i.e. 2A + C – D. A similar relationship of points to the network of parallels to OB and OD holds, and a chain O to P is 3B – 2D –A."
This property is unique to the knight, but these routes are not necessarily the shortest in number of moves. Murray continues: "Although Jaenisch decided that there was no formula giving the minimum length of the chain O to P on the lattice, we have only to plot the lengths of the minimum chain O to P for a number of positions of P to see that they must be governed by some law. The field surrounding O is divided into sectors by the vector directions OA, OB, etc, and the minimum chain O to P is conditioned by the bounding lines of the sector in which P is situated. In [the figure below] we give the lengths of the minimum chains from O to P in the sectors bounded by OA and OD' and by OA and OB."
Murray's rule, slightly simplified, is that: For points lying between OA and OD' and on the lines y = 2n–1 and y = 2n, and for points lying between the directions OA and OB and on or between the diagonals x+y = 3n+1 and x+y = 3n–2 the number of links in the minimum chain from O is n or n+1, the even number of these being on the cells of the same colour as O. The only exceptions to the rule are the cells (0,1), (1,1), (1,2), (2,1), (2,2) shown circled in the figure.
Example of restriction to a board with fixed edges: the knight takes two moves minimum to make a diagonal step (e.g. a2-c3-b1) but in the corner of most rectangular boards requires four moves to get from a1 to b2 (e.g. a1-b3-d2-c4-b2) and on the 3×3 board cannot make the journey at all.
Shortest (0,0) Journeys: The case of a closed path, when {p,q} = {0,0} was considered in the Note on Theory of Journeys. The shortest path is the null path, which means the piece just remains where it is. If it has to move a positive distance then the shortest journey is a switchback (one move out and back again). If it must not retrace any section of its path the shortest journey is a circuit of four moves, of which there are three geometrically different types (squares, diamonds and lozenges). If we must not make two moves in opposite directions the shortest path is of six moves: four rides of lengths 1, 1, 2, 2 in some sequence, forming a kite or bow shape. If we require a journey in the minimum number of rides without switchbacks, the answer is the 3, 4, 5 triangle of 12 moves. [??? is this true generally or only for knight???]
Shortest (0,1) Journeys: After the closed circuit the next case to consider is a path to an adjacent
cell, {p,q} = {0,1}. Consider the journey equations with p = 0, q = 1 (a single wazir step in direction 1).
(1) 0 = (A+D)r + (B+C)s and
(2) 1 = (B–C)r + (A–D)s.
For equation (1) to be true we must have, for some odd m:
(3) A+D = ms and B+C = –mr.
(m is odd, since, substituting the values of D and C from (3) into (2) gives
1 = (2A – ms)s + (2B + mr)r and if m is even the right-hand side is divisible by 2 and cannot equal 1).
Equation (2) is of the form 1 = Xr + Ys. If we can find any one solution (x,y) of this then the other
solutions are given by X = x + ns and Y = y – nr. We therefore require:
(4) B–C = x+ns and A–D = y–nr.
Equations (3) and (4) provide us with expressions for A, B, C, D in terms of x, y, m, n, r, s:
(5) A = (y–nr+ms)/2, B = (x–mr+ns)/2, C = –(x+mr+ns)/2, D = (–y+nr+ms)/2.
We must choose m and n so that these expressions represent whole numbers.
The problem in the above form was posed by A.I.Houston in the 1970s and he solved it for {r,s} = {z,z+1}, a case that includes knight, zebra and antelope. We see that (z+1)–z = 1, so x = –1 and y = 1. Trying m = 1 and n = 1 we calculate from (5): A = 1, B = 0, C = –z, D = z, so i = 2z+1.
Another family of cases is {r,s} = {1,2z}, which includes knight and giraffe. Here we can use 1+0(2z) = 1, which gives x = 1, y = 0. Taking m = 1 and n = 0 we find from (5): A = z, B = 0, C = –1, D = z and so again i = 2z+1.
These two cases, illustrated below, conform to the rule i = r+s. In general however r+s £ i.
The first cases not included in the above families are {2,5}, {2,7}, {2,9}, ... which are of the form {r,s} = {2,2z+1}. A general solution for this family proves a little more difficult. Noting that (2z+1)–2z = 1 we have x = –z, y = 1. Taking m = 1 and n = 0 we find from (5): A = z+1, B = –(z+2)/2, C = (z – 2)/2, D = z. This only gives whole numbers when z is even. For z = 2k, so that s = 4k+1, we have A = 2k+1, B = –(k+1), C = k–1, D = 2k, so i = 6k+1. This solves {2,5} in 7 moves and {2,9} in 13 moves. Choosing n = 1 instead we find: A = z, B = (z–1)/2, C = –(z+3)/2, D = z+1. This only gives whole number values when z is odd. For z = 2k–1, that is s = 4k–1, we have A = 2k–1, B = k–1, C = –(k+1), D = 2k, so i = 6k–1. This solves {2,7} in 11 moves.
Recreation: The first cases not covered by the above general rules are the {3,8} and {4,7} movers. Solve these cases and fit the journeys onto the smallest possible boards, and go on from there.