I've written a small Python script to give me the least number of moves it takes a knight to get from one square to any other on a $n{*}n$ chess board.
But then I've wondered how many paths the knight can take from one corner to the opposite one that use the minimal number of moves (i.e. on any $n{*}n$ board in $2*\Big\lceil{\frac{n-1}{3}}\Big\rceil$ moves, e.g. on a $8{*}8$ board in 6 moves).
So, I added another function to the code to "calculate" exactly that number by doing all possible paths from the opposite corner to the start where every step involves a decrease in the minimum number of moves needed to get to that square (which is calculated beforehand with the other function I mentioned at the beginning).
By now I have values for all $n$ from $1$ to $34$ (attached the list below). As you can see, the values get pretty big, which means it takes really long to calculate them using "brute-force" methods. Do you know of any way to calculate that number without the need of a computer trying all the possibilities?
Best Answer
The exact formula for the answer depends on $n \bmod 3$:
$$2 \left((k-1) (2 k+1)+\frac{3}{k}\right) \binom{2 k}{k-3}+2 \left(4 k+\frac{6}{k-1}+4\right) \binom{2 k}{k-2}+2 (2 k-1) k \binom{2 k}{k}$$
These only begin working for $n \ge 6$, because otherwise some cases below don't make sense - a "third" and "next-to-last" step might be the same, for instance. In addition to slogging through the cases by hand, I have confirmed that these give the same answer as the table for $6 \le n \le 34$.
Let's give the chessboard coordinates where we start at $(1,1)$ and end at $(n,n)$. Note that each knight's move from $(x,y)$, changing one coordinate by $\pm2$ and the other by $\pm1$, will change the sum $x+y$ by $-3$, $-1$, $1$, or $3$.
This gives a lower bound on the number of moves necessary: the sum needs to change by $2n-2$, and it can change by at most $+3$ per move, so at least $\lceil \frac{2n-2}{3}\rceil$ moves are necessary.
When $n=3k+1$, $\frac{2n-2}{3} = 2k$ exactly, so we can get from $(1,1)$ to $(n,n)$ in $2k$ moves only if every move changes $x+y$ by $3$. This means we make $k$ moves that are $(+1,+2)$ and $k$ moves that are $(+2,+1)$. Any permutation of these is fine, giving us $\binom{2k}{k}$ ways to get from $(1,1)$ to $(3k+1,3k+1)$ in $2k$ moves.
The next case by difficulty is $n=3k$. Here, we need $2k$ moves, but they only need to increase $x+y$ by $3k-2$, so we can have one move that increase $x+y$ by $+1$ instead of $+3$.
Suppose the unusual move is a $(+2,-1)$ move. Then to get to $(3k,3k)$ with $2k-1$ more moves that are $(+1,+2)$ or $(+2,+1)$, we must take $k-2$ moves that are $(+2,+1)$ and $k+1$ moves that are $(+1,+2)$. Moreover, $(+2,-1)$ cannot be the first or last move, since then we'd end up leaving the chessboard.
Using the formula $\frac{(a+b+c)!}{a! b! c!}$ for permutations of $a$ objects of one kind, $b$ of another, and $c$ of a third, we have $\frac{(2k!)}{1!(k-2)!(k+1)!}$ permutations total, and we must leave out $2 \cdot \frac{(2k-1)!}{(k-2)!(k+1)!}$ of them, for $(2k-2) \frac{(2k-1)!}{(k-2)!(k+1)!} = (2k-2) \binom{2k-1}{k-2}$ solutions.
There is an equal number of solutions with an unusual $(-1,+2)$ move, for $(4k-4) \binom{2k-1}{k-2}$ solutions total.
Finally, when $n=3k+2$, we cannot win in $2k$ moves, so we have $2k+2$ moves. Most moves will still be $(+2,+1)$ or $(+1,+2)$, but a few can follow a different pattern. I will omit the worst parts of the algebra, but here are the cases: