Distance formula for generalized knight movement on infinite chessboard from a corner

Consider a chessboard infinite in positive x and y directions, all square has non-negative integer coordinates, and the only corner is at $$(0,0)$$. A $$(p,q)$$-knight is a piece that can move so that after each move one of the coordinate change by $$p$$ and the other change by $$q$$ (we will just call it a knight from now on). Set a knight at the corner $$(0,0)$$, and assume that $$(p,q)$$ is such that every position on the board can be reached by the knight.

For a position $$(m,n)$$ on the board, let $$d(m,n)$$ be the minimum number of moves needed for a knight from the corner to reach $$(m,n)$$.

Now the following claims are true:

$$\gcd(p,q)=1$$ and $$p,q$$ are not both odd. This is necessary and sufficient conditions for every square to be reachable. Necessary is easily seen, for sufficient a sketch of the solution is in this question Can an $(a,b)$-knight reach every point on a chessboard?

For every square on the board, every ways to reach it require the number to moves to have the same parity as $$m+n$$, this is from black-white coloring. So $$d(m,n)$$ has the same parity as $$m+n$$

$$d(m,n)\max(p,q)>=\max(m,n)$$, obviously.

$$d(m,n)(p+q)>=m+n$$

So let's $$B(m,n)$$ be the smallest integer that satisfy all the constraints: $$B(m,n)\max(p,q)>=\max(m,n)$$ and $$B(m,n)(p+q)>=m+n$$ and $$B(m,n)$$ has the same parity as $$m+n$$. Then we know that $$d(m,n)>=B(m,n)$$ for all $$(m,n)$$. We make $$B(m,n)$$ the predicted value of $$d(m,n)$$.

DEFINITION: An "awkward spot" on the board is a position $$(m,n)$$ in which $$d(m,n)$$ is not equal to $$B(m,n)$$.

QUESTION: is it true that for all valid values of $$(p,q)$$ then the number of awkward spots are finite?

Example: for the normal chess knight $$(p,q)=(1,2)$$ then you can check against this answer chess board knight distance (but need some small modification since we start from a corner) to see that the awkward spots are $$(0,1),(1,0),(1,1),(2,2)$$ so there are only a finite number of them.

(I have heard suggestions to use Fourier transform but I have no clues what to do with it)

1 Answer

If I understand you correctly, the number of "awkward spots" can easily be infinite. This is mainly because, in a sense, your definition of $$B(m,n)$$ is a bit too "optimistic".

Consider $$(p,q) = (1,10)$$.

Obviously any square $$(k, 10k)$$ can be reached in exactly $$k$$ moves. What about $$(k, 10k-2)$$, for $$k \ge 1$$? We have $$B(k, 10k-2) = k$$ because:

• $$k \max(1,10) = 10k \ge \max(k,10k-2) = 10k-2$$

• $$k (1 + 10) = 11k \ge k + (10k-2) = 11k - 2$$

• $$k$$ has same parity as $$k + (10k-2)$$

• OTOH $$(k-1) (1 + 10) = 11(k-1) < 11k -2$$

However, the square $$(k, 10k-2)$$ cannot be reached in $$k$$ moves (or fewer for that matter), because:

• If all $$k$$ moves are of the form $$(\pm 1, +10)$$ then the final $$y$$-coordinate would be $$10k$$ and not $$10k-2$$.

• If at least one move is not $$(\pm 1, +10)$$ then the final $$y$$-coordinate is at most $$10(k-1) + 1 = 10k -9 < 10k-2$$.

Conclusion: For the $$(1,10)$$-knight, $$(k, 10k-2)$$ (and many similar squares) are awkward for any $$k \ge 1$$.

Further thoughts: in general for a $$(p,q)$$-knight to move to row $$r$$ (regardless of column) already requires something like solving the Bezout identity $$px + qy = r$$ with "minimum" coefficients $$(x,y)$$, in a sense. My example shows that forgetting this bound already makes your $$B(m,n)$$ too optimistic. A more interesting question is if you somehow include this in the definition of $$B(m,n)$$, then are there infinite number of awkward squares? I don't know the answer to that question.

• This looks correct, thanks. Interesting, it looks like this problem is even harder than I thought. Perhaps this formula only work for a few small value of $(p,q)$. Maybe I should think about this some more. – calcstudent Dec 27 '19 at 0:28
• It seems even including the Bezout condition is insufficient. E.g. the $(1,10)$-knight needs $5$ moves to reach row $y=5$, or reach column $x=5$, but what is $d(5,5)$? By your original definition, $B(5,5) = 1$. If you include the Bezout condition, you might say $B'(5,5) = 5$. But it cannot reach $(5,5)$ in $5$ steps, because to reach $y=5$ row it must do $(\pm 10, +1)$ five times. Now this isn't to say the number of awkward spots (w.r.t. new $B'(m,n)$) is still infinite. But I do think a general logic for $d(m,n)$ is very interesting, and possibly very hard... at least for me. :) – antkam Dec 27 '19 at 0:33