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.)
Combinatorics – Minimum Moves for a Knight to Reach a Cell on a Chessboard
combinatorics
Related Solutions
The problem is a Markov chain, and we can attack it with linear algebra!
First, we can simplify the problem by exploiting the symmetry of both the knight's movement and the chessboard. Let's add the following rule:
- After every move, the knight is reflected across the horizontal, vertical, and diagonal axes of symmetry, until it rests in the upper-left triangle of $10$ squares.
In other words, the legal positions are 1a, 1b, 1c, 1d, 2b, 2c, 2d, 3c, 3d, and 4d. You can visualize these positions as occupying one of the $8$ triangles in this diagram:
Now, there are $11$ positions that the knight can occupy after a move: the $10$ positions just named, and $1$ position representing not-on-the-board. For $i,j\in[1,11]$, let $P_{i,j}$ be the probability of transitioning from $i$ to $j$. There are $11\times11=121$ probabilities to calculate, and I suspect that this part must be done by hand.
Now we have an $11\times11$ square matrix $P$. For all $n$, the matrix power $P^n$ is the transition matrix for $n$ moves! So, let's arbitrarily index the initial square as $i=1$ and the off-the-board position as $j=11$. Then the probability of leaving the board after $n$ moves is $(P^n)_{1,11}$, and the probability of staying on the board is: $$1-(P^n)_{1,11}$$ That's as far as I can take you. You could express this formula more explicitly by calculating $P$ and then finding its Jordan normal form. Then you'll have a formula for the powers $P^n$, and you can pull out whatever matrix element you want. If you've seen the explicit formula for the Fibonacci numbers, it's the same principle, but with a larger matrix!
Edit: You've commented that if the knight is in the center of the board, then it can't exit the board in $1$ move. This is a useful obvservation. If we index positions 3c, 3d, and 4d as $i=8,9,10$, then it tells us that $P_{8,11}=P_{9,11}=P_{10,11}=0$. So you see, the matrix $P$ can represent pretty much everything we know about the problem.
Another example of reading information from $P$: You have a rule that if the knight leaves the board, it can't come back. This translates to the statement that $P_{11,11}=1$, and for all $j<11$, $P_{11,j}=0$. Between this paragraph and the previous paragraph, we already know $14$ matrix elements. There are just $107$ more to calculate...
Edit 2: Another example. You commented that from the initial position, only $2$ out of $8$ possible moves stay on the board. That tells us that $P_{1,11}=3/4$. The knight can stay on the board by moving to 2c or 3b. In my scheme, 3b gets reflected back to 2c. So if we index 2c as $j=6$, then $P_{1,6}=1/4$. For all other $j$ besides $6$ and $11$, we have $P_{1,j}=0$. That's another $11$ matrix elements calculated; $96$ to go...
Using the natural ordering of squares of an $n \times n$ board $(i,j)\rightarrow ni+j$, here are optimal solutions for $n=4,5,6$. Clearly there are no solutions for $n < 4$.
$$ \begin{align} K(4) \; &: \; (0, 1, 5, 6, 10, 11) \\ K(5) \; &: \; (0, 1, 3, 6, 11, 12, 13) \\ K(6) \; &: \; (7, 8, 9, 10, 19, 20, 21, 22) \\ \end{align} $$
For $n=7$ I ran a brute force and exhausted all sets of < 10 knights. So, your solution of 10 knights is optimal.
I found a greedy algorithm that works pretty well -- I found 6 different optimal solutions for n=7.
$$ (3, 15, 16, 18, 19, 29, 30, 31, 32, 33) \\ (9, 11, 16, 18, 21, 25, 30, 32, 37, 39) \\ (9, 11, 16, 18, 23, 25, 30, 32, 37, 39) \\ (9, 11, 16, 18, 23, 27, 30, 32, 37, 39) \\ (15, 16, 17, 18, 19, 29, 30, 31, 32, 33) \\ (15, 16, 17, 18, 19, 29, 30, 32, 33, 45) \\ $$
First construct the $directed$ graph where each vertex is a square on the board and each edge $(u,v)$ represents a possible knight move from $u$ to $v$. Let's take a look at the adjacency matrix.
We want to find the smallest subset of rows (places to put the knights) such that each column remains non-empty (every square is attacked). This led me to do the following. Repeating until all pieces are attacked: greedily choose the safest spot on the board, that is, the non-attacked vertex $v^*$ with the minimum number of incoming edges. Let $u^*$ be the most aggressive of $v^*$s possible attackers. That is, let $u^*$ be the element in $\{ u \; | \; \exists \; (u,v^*) \} $ with the maximum number of outgoing edges. Let $U$ be the set of vertices that $u^*$ can attack $U = \{v \; | \; \exists \; (u^*,v)\}$. Place a knight on position $u^*$ and mark vertices in $U$ as attacked and remove all of their incoming edges.
Here is a visual of the first step. Note $v^*$ is the column with the least number of nonzero elements.
Best Answer
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.