Function kmf(x,y) is the minimum number of moves for a knight to move x units to the right and y units forward.
(1) Find kmf(x,y) for non-negative integer values of x and y from 0 to 7.
(2) Can you find an expression for kmf(x,y) in terms of x and y?
Notes:
Assume this is an infinite chess board so there are no edge-of-the-board boundary issues.
To avoid duplication, ignore cases where y is less than x.
We give a functional form for km(x,y), for positive x,y, and y>x,
This provides the full function because of the symmetry:
km(x,y)=km(y,x) and km(-x,y)=km(x,y)
The function consists of 3 parts: The central region, and the upper
and lower fans as shown below. The knight starts at 0 and the number
given is the least number of moves.
The central region where y<3 has distances from supplied constants.
2 1 4 km(0,2)=2, km(1,2)=4, and km(2,2)=4
3 2 km(0,1)=3, km(1,1)=2
0 km(0,0)=0
The lower fan where [(y-1)/2] <= x is given by
km(x,y) = mod(x+y,3) + [(x+y)/3], where [ ] is the floor function.
The upper fan where [(y-1)/2] > x is given by
km(x,y) = k(mod( (y-3) + 2*mod(x,2),4) ) +2*[(y-2*x-3)/4] + x
and k(0)=3, k(1)=2, k(2)=3 and k(2)=4
These formulae are motivated below.
upper fan
10 11 10 11 10 11 10 11 10|11 10 11 12 11 12 13 12 13 14 13 14
11 10 11 10 11 10 11 10 11|10 11 10 11 12 11 12 13 12 13 14
10 9 10 9 10 9 10 9|10 9 10 11 10 11 12 11 12 13 12
9 10 9 10 9 10 9 10| 9 10 9 10 11 10 11 12 11 12
8 9 8 9 8 9 8 |9 8 9 10 9 10 11 10 11 12
9 8 9 8 9 8 9 |8 9 8 9 10 9 10 11 10
8 7 8 7 8 7 |8 7 8 9 8 9 10 9 10
7 8 7 8 7 8 |7 8 7 8 9 8 9 10
6 7 6 7 6 |7 6 7 8 7 8 9 8
7 6 7 6 7 |6 7 6 7 8 7 8 lower
6 5 6 5 |6 5 6 7 6 7 8 fan
5 6 5 6 |5 6 5 6 7 6
4 5 4 |5 4 5 6 5 6
5 4 5 |4 5 4 5 6
*4 3 |4 3 4 5 4
*3 4 |3 4 3 4
*2 |3 2 3 4
*3 |2 3 2
---------------
2 1 4
3 2 central region
0
Motivation:
To understand the central region we review the 8 initial
places the knight can go from 0
- 8 - 1 -
7 - - - 2
- - 0 - -
6 - - - 3
- 5 - 4 -
We track some of these paths forward, where the first number
indexes the starting move and the number in parentheses counts
subsequent moves, including some branches. E.g., take 4 moves,
starting with 6(1) to get to (+2,+2) at 6(4)
---- 8(1) 7(2) 1(1) 6(4)
7(1) ---- 7(3) 8(2)
---- ---- -(0) 6(3)
6(1) 7(2) ---- ----
---- ---- 6(2) ----
The the number of mores needed to occupy the central positions
are taken as constants, as shown.
2 1 4
3 2
0
Additionally, three positions in the top row above:
8(1), 7(2), and 1(1), are the jumping-off points for the lower
fan. The figure below traces the 1-thread, the 7-thread, and the
8-thread, all progressing with moves of (+1,+2) or (+2,+1) only.
Therefore, each move increases (x+y) by 3, and so the
number of moves needed to get that position is (x+y)/3, plus an
an initial delta given by mod(x+y,3).
The minimum knight moves in the lower fan this comes out to:
km(x,y) = mod(x+y,3) + [(x+y)/3], where [ ] is the floor function.
- - - - - - - - - 7 1 8 7 1 8 7 1 8 7 1 8
- - - - - - - - - 8 7 1 8 7 1 8 7 1 8 7
- - - - - - - - 7 1 8 7 1 8 7 1 8 7 1
- - - - - - - - 8 7 1 8 7 1 8 7 1 8
- - - - - - - 7 1 8 7 1 8 7 1 8 7
- - - - - - - 8 7 1 8 7 1 8 7 1
- - - - - - 7 1 8 7 1 8 7 1 8
- - - - - - 8 7 1 8 7 1 8 7
- - - - - 7 1 8 7 1 8 7 1
- - - - - 8 7 1 8 7 1 8
- - - - 7 1 8 7 1 8 7 lower fan
- - - - 8 7 1 8 7 1
- - - 7 1 8 7 1 8
- - - 8 7 1 8 7
- - 7 1 8 7 1
- - 8 7 1 8
- 7 1 8 7
- 8 7 1
8 7 1 (jumping-off points)
In the upper fan, we see the vertical string (*4 *3 *4 *2) as marked
above, progress upward in the first column (x=0) and also to the right,
as seen below. The numbers represent the minimum number of moves needed.
- Here the "-" separates groups of 4 that march upward in a group,
7 with each term gaining +2 each time, and right, each gaining +1.
- 6 In the upper fan, movement in the y direction is less efficient
6 5 because y>>x, and the knight must waste (+/-) x-movement (-1,2),
5 6 (+1,2) to accomplish y-movement. These extra moves are added to
4 - the [(x+3)/3] term in the formulation. The last terms provide
5 5 the +2 upward and +1 rightward additions.
- 4
*4 3
*3 4
*2 -
*3
The upper fan where [(y-1)/2] > x is given by
km(x,y) = k(mod( (y-3) + 2*mod(x,2),4) ) +2*[(y-2*x-3)/4] + x
and k(0)=3, k(1)=2, k(2)=3 and k(2)=4
Edited on November 18, 2024, 1:39 am
soln, part 2
