Given two squares on an 8×8 chess board, how can we determine the minimum number of moves required by a knight to reach one square starting from the other?
[Math] minimum number of steps for knight in chess
combinatorics
Related Solutions
For a $6 \times 3$ board, it's impossible. Consider the board below, and the squares, marked with an $\times$.
$$\begin{matrix} \cdot & \cdot & * & \cdot & \cdot & \cdot \\ \times & \cdot & \cdot & \cdot & \times & \cdot \\ \cdot & \cdot & * & \cdot & \cdot & \cdot \\ \end{matrix}$$
The only way to get to these squares is through the squares marked with an $\ast$. But if you use both to get to one of them and to get out again, then you cannot reach the other marked square anymore. The only way to solve this is to start at one of these marked squares. By symmetry, we have two other such squares:
$$\begin{matrix} \cdot & \cdot & \cdot & \ast & \cdot & \cdot \\ \cdot & \times & \cdot & \cdot & \cdot & \times \\ \cdot & \cdot & \cdot & \ast & \cdot & \cdot \\ \end{matrix}$$
So we have to finish at another of these squares as well. So the first four and final four moves are determined, as, one of the following two scenarios:
$$\begin{matrix} \cdot & \cdot & 2 & 15 & \cdot & \cdot \\ 1 & 16 & \cdot & \cdot & 3 & 18 \\ \cdot & \cdot & 4 & 17 & \cdot & \cdot \\ \end{matrix} \qquad \text{or} \qquad \begin{matrix} \cdot & \cdot & 2 & 17 & \cdot & \cdot \\ 1 & 16 & \cdot & \cdot & 3 & 18 \\ \cdot & \cdot & 4 & 15 & \cdot & \cdot \\ \end{matrix}$$
In both cases, we need the remaining $10$ squares to connect the two ends of the chain to form a knight's path. This means that each of these $10$ points is connected to two other of these points (except for the ones next to $2$ and $17$). By starting with the corners, we get two chains of length $5$:
$$\begin{matrix} d & a & \cdot & \cdot & A & D \\ \cdot & \cdot & c & C & \cdot & \cdot \\ b & e & \cdot & \cdot & E & B \end{matrix}$$
There's just no way to connect $a/e$ to $A/E$, so there's no chain of length $10$ connecting these squares. So there is no knight's path on this board.
This is just illustration for what @Henning Makholm described:
(if somebody is interested in the implementation of this simulation, the code is here)
It looks that closed form of number of squares on infinite chessboard reachable at <= n knight's moves from a fixed square is known as A018836, and is following:
$$K_n = 1-6*n+14*n^2+4*sign(n*(n-1)*(n-3))$$.
Best Answer
If you were considering an infinite chess board, you might get a solution as a (slightly complicated) formula, but on a finite board the restriction of edges (and especially corners) does affect things. Obviously you can draw maps:
And there you can see that the corner position of the knight means that it is quite slow to reach its diagonally neighbouring square, whereas with an open-board knight:
diagonally-adjacent squares are reached more quickly.
Additional thought:
Outside the $5\times 5$ square centred on the knight, the move-distance pattern becomes simpler. Then if you find $\Delta x, \Delta y$ (unsigned), compute the maximum of $\left ( \frac{\Delta x}{2},\frac{\Delta y}{2},\frac{\Delta x+\Delta y}{3} \right )$ and round up to the nearest integer. Call this $m'$. Now calculate the move count $m$ as follows: $$ m=m'+((m'+\Delta x+\Delta y) \bmod 2) $$ To handle close-in squares (on a board of at least $5\times 5$) we can list the exceptions: $$ \begin{align} \Delta x =\Delta y =2 &\implies m=4 \\ \Delta x+\Delta y =1 &\implies m=3 \\ \text{For a knight in a corner only, }\Delta x=\Delta y =1 &\implies m=4 \hspace{3in} \end{align}$$