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.)

  • 3
    $\begingroup$ I'm not immediately sure, but it's easy to bound above. We know, for instance, that it should take less than say $m/2 + n/2 + 8$ moves. $\endgroup$ – davidlowryduda Feb 1 '12 at 19:32
  • $\begingroup$ You can solve it with dynamic programming but I'm not aware about availability of combinatorics proof, do you interested in algorithmic solution? $\endgroup$ – Saeed Feb 1 '12 at 19:48
  • $\begingroup$ @Saeed Absolute value of m and n can be as large as one billion. So dynamic programming doesn't work I think. I'll appreciate any kind of solution and proof but as elementary as possible. $\endgroup$ – f.nasim Feb 1 '12 at 20:15
  • $\begingroup$ @mixedmath I find it here actually. Does it belong to homework? $\endgroup$ – f.nasim Feb 1 '12 at 20:17
  • 3
    $\begingroup$ A lower bound for the number of moves is $(m+n)/3$, simply because a knight's move gains at most three squares in the north/east directions. If $n/2\le m\le 2n$ then the answer is presumably between $(m+n)/3$ and $(m+n)/3 + C$ for some small constant $C$. When one of $m$ and $n$ is much greater than the other, then the answer is probably closer to $\max\{m,n\}/2$. Note also that the exact answer might well depend a little on the value of $m+n\pmod 3$, since every knight's move changes this value by $\pm1$. $\endgroup$ – Greg Martin Feb 1 '12 at 20:43

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.

  • $\begingroup$ Could you elaborate these two arguments: > the number of moves to get from $(x,x)$ to the origin is $2\lfloor \frac{x+2}{3} \rfloor$ and > the number of moves from $(x,0)$ to origin is $x - 2\lfloor \frac{x}{4} \rfloor$ $\endgroup$ – f.nasim Feb 2 '12 at 9:59
  • 2
    $\begingroup$ It takes 2 moves to get from $(x+3,x+3)$ to $(x,x)$, or from $(x+4,0)$ to $(x,0)$. This explains the factor of 2, and the denominators 3 and 4. To adjust it to the exact form, look at the values near the origin, which you can work out by hand. $\endgroup$ – TonyK Feb 2 '12 at 11:49
  • $\begingroup$ @TonyK A little late to the party but a few questions: 1) Why should we assume m >= n? 2) Would it matter if m or n is non-negative? 3) Does your insight work for non-knight moves too? I.e lets say that from a given square you can make a move to your surrounding 8 squares. Then by what factor would you backtrack from the goal to get close to the origin? $\endgroup$ – ForeverLearning Aug 18 '14 at 19:37
  • $\begingroup$ @TonyK what about (1,1)? Coming from (9,5), (7,4), (5,3), (3,2). $\endgroup$ – Jonatas Walker May 31 '16 at 10:18
  • $\begingroup$ Oh no, how this is wrong! Test (8,0) to (0,0) or (9,0) to (0,0). $\endgroup$ – Jonatas Walker May 31 '16 at 13:56

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.

  • 1
    $\begingroup$ That's just dynamic programming. For $m,n$ in the region of a billion, it's not practical. $\endgroup$ – TonyK Feb 1 '12 at 23:16
  • $\begingroup$ I'm aware that the formula I quoted is not practical for large $m,n$, which is why I encouraged OP to work on getting a closed form out of it. $\endgroup$ – Gerry Myerson Feb 1 '12 at 23:30
  • 2
    $\begingroup$ Dynamic programming was already mentioned (and dismissed) in the early comments to the OP. As for a closed form, have a look at my answer :-) $\endgroup$ – TonyK Feb 1 '12 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.