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.
part 1
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
0
Here the knight starts at 0.
part 2
The general larger view (for the first quadrant)
for x and y from 0 to 20 (but allowing the knight
full freedom to visit other quadrants) is:
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 13
10 9 10 9 10 9 10 9 10 9 10 11 10 11 12 11 12 13 12 13 14
9 10 9 10 9 10 9 10 9 10 9 10 11 10 11 12 11 12 13 12 13
8 9 8 9 8 9 8 9 8 9 10 9 10 11 10 11 12 11 12 13 12
9 8 9 8 9 8 9 8 9 8 9 10 9 10 11 10 11 12 11 12 13
8 7 8 7 8 7 8 7 8 9 8 9 10 9 10 11 10 11 12 11 12
7 8 7 8 7 8 7 8 7 8 9 8 9 10 9 10 11 10 11 12 11
6 7 6 7 6 7 6 7 8 7 8 9 8 9 10 9 10 11 10 11 12
7 6 7 6 7 6 7 6 7 8 7 8 9 8 9 10 9 10 11 10 11
6 5 6 5 6 5 6 7 6 7 8 7 8 9 8 9 10 9 10 11 10
5 6 5 6 5 6 5 6 7 6 7 8 7 8 9 8 9 10 9 10 11
4 5 4 5 4 5 6 5 6 7 6 7 8 7 8 9 8 9 10 11 10
5 4 5 4 5 4 5 6 5 6 7 6 7 8 7 8 9 10 9 10 11
4 3 4 3 4 5 4 5 6 5 6 7 6 7 8 9 8 9 10 11 10
3 4 3 4 3 4 5 4 5 6 5 6 7 8 7 8 9 10 9 10 11
2 3 2 3 4 3 4 5 4 5 6 7 6 7 8 9 8 9 10 11 10
3 2 3 2 3 4 3 4 5 6 5 6 7 8 7 8 9 10 9 10 11
2 1 4 3 2 3 4 5 4 5 6 7 6 7 8 9 8 9 10 11 10
3 2 1 2 3 4 3 4 5 6 5 6 7 8 7 8 9 10 9 10 11
0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 9 8 9 10 11 10
Generating this is easy. Start with the knight at zero.
Next use all 8 possible moves to fill 8 empty squares.
Then keep repeating, emanating 8 moves from each new position
to see if the knight reaches a new square.
Let us take the 5 x 5 block of km(x,y) for (0<=x<4 and 0<=y<4)
as initial conditions. Include additional initial conditions the
two lines km(x,0) x = 0,1,2,... and km(0,y) y=0,1,2,...
These are simply: 0 3 2 3 2 3 4 5 4 5 6 7 6 7 8 9 8 9 ...
We note that all other shortest paths for the knight are
are given by a combined sequence of movements in the (+1,+2) and/or
the (+2,+1) directions from these initial positions and fill the quadrant.
Edited on November 14, 2024, 10:17 pm
soln
