Minimum number of moves to reach a cell in a chessboard by a knight

Given an infinite chessboard represented as a 2D Cartesian plane. A knight is placed at the origin. What is the minimum number of moves it needs to reach a cell $(m,n)$? (Without loss of generality, we might as well assume that $m$ and $n$ are nonnegative integers.)

Solution 1:

After a bit of doodling, I have persuaded myself of the following:

To get to the origin in the fewest moves, always make the move (or one of the moves) that takes you closest to the origin, that is not to (0,1), or (2,2), or a reflection of one of these cells.

Perhaps after a bit more doodling, I'll come up with some kind of proof.

Updated to answer the question: If the above is true, then we can proceed as follows:

We may assume $m \ge n$. Then we repeat the move $(-2,-1)$ until we reach either the diagonal or the $x$-axis (I'm running the film backwards here, from $(m,n)$ to $(0,0)$).

If $m \ge 2n$, this takes $n$ moves, and ends up at $(m-2n,0)$.
If $m \le 2n$, this takes $m-n$ moves, and ends up at $(2n-m,2n-m)$.

So we only need to know how many moves are required from the diagonal or the $x$-axis.

For the diagonal, the number of moves to get from $(x,x)$ to the origin is $$2\lfloor \frac{x+2}{3}\rfloor $$ except for the anomalous point $(2,2)$, which requires 4 moves, not 2. But unless our starting point was $(2,2)$, we can ignore this anomaly $-$ coming from point $(4,3)$, we don't move to $(2,2)$, but to $(3,1)$, which requires 2 moves.

For the $x$-axis, the number of moves required to get from $(x,0)$ to the origin is $$x - 2\lfloor\frac{x}{4}\rfloor$$

except for the anomalous point $(1,0)$, which requires 3 moves, not 1. But unless our starting point was $(1,0)$, we can ignore this anomaly $-$ coming from point $(3,1)$, we don't move to $(1,0)$, but to $(1,2)$, which requires 1 move.

From this, it is easy to construct an explicit formula, if that's what you want; you only have to treat the starting points $(2,2)$ and $(1,0)$ as special cases.

Solution 2:

The answers are tabulated here at the Online Encyclopedia of Integer Sequences. A formula is also given there, but it has a recursive component: for $m$ and $n$ at least 2, it gives $$T(m,n)=1+\min(T(m-2,n-1),T(m-1,n-2))$$ You could work on turning that into a closed form.