//////////////////////////////////////////////////////////////////////////////// Knight's Move Distance Function _______________________________ *Define* [X, Y] := [|x|, |y|] if |x| >= |y| , := [|y|, |x|] otherwise; p := X-Y; q := p-Y; r := 3 if q < 0 , := 4 otherwise; f(x, y) := 3 if [X, Y] = [1, 0] , := 4 if [X, Y] = [2, 2] , := p - 2*Floor(q/r) otherwise; *Lemma* For f(x, y) > 4 in the first octant x >= y >= 0 , f(x, y) = f(x-2, y-1) + 1 . Proof: Note [x', y'] = [x-2, y-1] lies also in the first octant unless x = y . Then correspondingly p' = p-1 , q' = q , r' = r , and via definition f' = f-1 . QED *Theorem* Denoting by d(x, y) knight's move distance from [0, 0] , d(x, y) = f(x, y) . Proof: via symmetry, need consider only the first octant. For f(x, y) > 4 by induction on f : d(x, y) <= d(x-2, y-1) + 1 via definition, = f(x-2, y-1) + 1 via hypothesis, = f(x, y) via lemma; but d(x, y) > f(x-2, y-1) via hypothesis, therefore d(x, y) = f(x, y) . For f(x, y) <= 4 : by inspection of table below, showing d(x, y) = f(x, y) for 0 <= x,y <= 8 . [0 3 2 3 2 3 4 5 4] [3 2 1 2 3 4 3 4 5] [2 1 4 3 2 3 4 5 4] [3 2 3 2 3 4 3 4 5] [2 3 2 3 4 3 4 5 4] [3 4 3 4 3 4 5 4 5] [4 3 4 3 4 5 4 5 6] [5 4 5 4 5 4 5 6 5] [4 5 4 5 4 5 6 5 6] QED *Remark* Above, cell [0, 0] is assumed to lie at board centre; if instead it lay at top left corner, the definition would require another special case: f(x, y) := 4 if [X, Y] = [1, 1] . *Geometry* Cells [x, y] lying at distance c = d(x, y) > 4 form an octagonal annulus, with straight sides comprising four aligned with rook moves (q >= 0 above), and isomorphic to { [x,y] | 3c-4 <= x+y <= 3c & c < x < 2c & x+y = c (mod 2) } ; and four with bishop moves (q < 0 above), isomorphic to { [x,y] | c <= y-x & c <= y+x & 2c-3 <= y <= 2c & x+y = c (mod 2) } . Neglecting cells not having the same parity x+y = c (mod 2) , each annulus disconnects the remainder into regions at distance <= c-2 and >= c+2 respectively. The induction then becomes visually obvious. Fred Lunnon, Maynooth 01/04/14 ////////////////////////////////////////////////////////////////////////////////