How to calculate the number of paths of minimum length possible a knight can take to get from one corner of a chess board to the opposite one?

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?

5 Answers

The exact formula for the answer depends on $n \bmod 3$:

• When $n=3k$, there are $(4k-4)\binom{2k-1}{k-2}$ shortest paths, which have length $2k$.
• When $n=3k+1$, there are $\binom{2k}{k}$ shortest paths, which have length $2k$.
• When $n=3k+2$, there is a rather awful number of shortest paths, which have length $2k+2$:

$$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:

• One move by $(-2,+1)$, $k-1$ moves by $(+1,+2)$, and $k+2$ moves by $(+2,+1)$. Here, $(-2,+1)$ cannot be the first or last; it cannot be the second unless it is preceded by $(+2,+1)$; it cannot be the next-to-last unless it is followed by $(+2,+1)$. There are $(4+\frac{6}{k-1}+4k) \binom{2k}{k-2}$ paths of this type.
• An equal number of paths have one move by $(+1,-2)$, $k-1$ moves by $(+2,+1)$, and $k+2$ moves by $(+1,+2)$.
• Two moves by $(+2,-1)$, $k-3$ moves by $(+2,+1)$, and $k+3$ moves by $(+1,+2)$. Here, a $(+2,-1)$ move cannot be the first or last; also, the beginning cannot be $(+2,+1), (+2,-1), (+2,-1)$, and the end cannot be the reverse of this sequence. There are $(\frac3k + (k-1)(2k+1))\binom{2k}{k-3}$ such paths.
• An equal number of paths that have two moves by $(-1,+2)$, $k-3$ moves by $(+1,+2)$, and $k+3$ moves by $(+2,+1)$.
• One move by $(+2,-1)$, one move by $(-1,+2)$, $k$ moves by $(+1,+2)$, and $k$ moves by $(+2,+1)$. Here, the two special moves cannot be first or last. There are $2k(2k-1)\binom{2k}{k}$ such paths.

What do you mean by "brute force" methods? Here is one possible method.

Mark the initial cell with a $0$. Mark all the cells you can reach in one step with a $1/1$. Mark any unmarked cell you can reach from a $1/1$ square with a $2/?$, where $?$ is the number of cells with a $1/1$ mark that see it. At stage $n+1$ mark each of the unmarked cells which sees a cell with an $n/-$ with $n+1/a$, where $a$ is the sum of the second digits of the $n/-$ cells it sees. The first entry for each cell is the number of moves required to get there. The second entry is the number of minimum paths.

There will be ways of making the marking efficient

I think that if you study edge effects you might be able to be more efficient in going from side $N$ to side $N+1$

Not an answer, but too long for a comment.

Every third entry starting at the 2 in position 4 is , the sequence of central binomial coefficients $$ \binom{2 n}{n} = \frac{2n !}{(n!)^2}. $$

Perhaps you can show that your set of knight paths matches one of the many sets that sequence counts.

The other two sequences corresponding to entries at positions $3k$ and $3k+2$ are not in OEIS. You may want to submit them and your full sequence for inclusion. You should certainly add the $3k+1$ counts to the entry at A000984 .

Update: I have computed the number of paths for $n=2002$ using big-number arithmetic. This takes about 33 seconds on my 5-year-old laptop. The number is:

8190208784729436886356117773784622775755067282053423716575500202735560465709335900585530071710859537760593235327498105781176271785594652396288612704784180275010456911676357127385702548323013423782254451054730068584395141019425114314509616197232957876449930811996587519674097859439211473946990204079217310697700619432286128120250036903378923748348374097572269452418134055306511575856760953692422184640 

This agrees with the expected value $\binom{1334}{667}$, according to Wolfram Alpha.

I have implemented Mark Bennet's suggestion in C++, and it agrees with your figures up to $n=34$. The computation of all side lengths up to $n=84$ is instantaneous to a human eye. It uses 64-bit unsigned integer arithmetic, which overflows when it reaches $n=85$. Here is the output for $3\le n\le 84$:

 3: 4 2 4: 2 2 5: 4 8 6: 4 4 7: 4 6 8: 6 108 9: 6 40 10: 6 20 11: 8 858 12: 8 252 13: 8 70 14: 10 5596 15: 10 1344 16: 10 252 17: 12 32814 18: 12 6600 19: 12 924 20: 14 179696 21: 14 30888 22: 14 3432 23: 16 937794 24: 16 140140 25: 16 12870 26: 18 4721964 27: 18 622336 28: 18 48620 29: 20 23127208 30: 20 2720952 31: 20 184756 32: 22 110809672 33: 22 11757200 34: 22 705432 35: 24 521527428 36: 24 50338904 37: 24 2704156 38: 26 2418585240 39: 26 213955200 40: 26 10400600 41: 28 11077901930 42: 28 903960720 43: 28 40116600 44: 30 50207576760 45: 30 3800379240 46: 30 155117520 47: 32 225494871090 48: 32 15910951500 49: 32 601080390 50: 34 1004794266060 51: 34 66378132480 52: 34 2333606220 53: 36 4446461479680 54: 36 276075168600 55: 36 9075135300 56: 38 19556902924680 57: 38 1145186547120 58: 38 35345263800 59: 40 85551558522060 60: 40 4739294943240 61: 40 137846528820 62: 42 372431743412040 63: 42 19573013616000 64: 42 538257874440 65: 44 1614240684199260 66: 44 80687621130480 67: 44 2104098963720 68: 46 6969068512044288 69: 46 332081706013200 70: 46 8233430727600 71: 48 29979434963763828 72: 48 1364718587868792 73: 48 32247603683100 74: 50 128543887400990456 75: 50 5600962254472704 76: 50 126410606437752 77: 52 549513851822624304 78: 52 22959191340190000 79: 52 495918532948104 80: 54 2342667576290926416 81: 54 94009360838437408 82: 54 1946939425648112 83: 56 9961870432209101896 84: 56 384544513652024880 

If you used big-number arithmetic, you could continue into the thousands without your CPU breaking into a sweat.

In case anybody is interested, here is the source code for the 64-bit version (posted as is, without comments, and with absolutely no after-sales service):

#include <stdio.h> #include <stdint.h> #include <string.h> #include <stdlib.h> static int nSteps[1000][1000] ; static uint64_t nPaths[1000][1000] ; static const struct { int x ; int y ; } MoveList[8] = { { 1, 2 }, { 1, -2 }, { 2, 1 }, { 2, -1 }, { -1, 2 }, { -1, -2 }, { -2, 1 }, { -2, -1 }, } ; int main (int argc, char** argv) { for (int n = 3 ; n <= 1000 ; n++) { memset (nSteps, 0, sizeof (nSteps)) ; memset (nPaths, 0, sizeof (nPaths)) ; nSteps[1][2] = nSteps[2][1] = 1 ; nPaths[0][0] = nPaths[1][2] = nPaths[2][1] = 1 ; for (int Step = 2 ; ; Step++) { bool Changed = false ; for (int i = 0 ; i < n ; i++) for (int j = 0 ; j < n ; j++) if (nPaths[i][j] == 0) for (int move = 0 ; move < 8 ; move++) { int x = i + MoveList[move].x ; int y = j + MoveList[move].y ; if (x >= 0 && y >= 0 && x < n && y < n && nSteps[x][y] == Step - 1) { nSteps[i][j] = Step ; nPaths[i][j] += nPaths[x][y] ; if (nPaths[i][j] < nPaths[x][y]) printf ("\n*** OVERFLOW ***\n"), exit (1) ; Changed = true ; } } if (!Changed) break ; } printf ("%2d: %2d %I64u\n", n, nSteps[n-1][n-1], nPaths[n-1][n-1]) ; } } 

The sequence $a(n), n\geq 0$ \begin{align*} 1,0,2,2,8,4,6,\color{blue}{108},40,20,858,252,70,5\,596,1\,344,252,\ldots\tag{1} \end{align*} giving the wanted number of shortest knight paths in an $(n\times n)$ board from the left bottom corner to the top right corner is stored as A120399 in OEIS.

The following formula for $a(n), n>3$ is stated: Let \begin{align*} K=K(n)=2\left\lfloor\frac{n+1}{3}\right\rfloor \end{align*} be the shortest path length. Then $a(n), n>3$ is given as \begin{align*} a(n)&=2(K-2)\binom{K-1}{K/2-2}&n\equiv0\mod(3)\\ a(n)&=\binom{K}{K/2}&n\equiv1\mod(3)\\ a(n)&=(K-2)(K-3)\binom{K-2}{K/2-1}\\ &\qquad+2\left((K-2)\binom{K-1}{K/2-2}-2\binom{K-2}{K/2-3}\right)&n\equiv2\mod(3)\\ &\qquad+2\left(\binom{K-2}{2}\binom{K-2}{K/2-4}-2\binom{K-3}{K/2-5}\right) \end{align*}

Example: ($n=8$)

We calculate the number of shortest paths for the $(8\times 8)$ board. We obtain \begin{align*} K=K(8)=2\left\lfloor\frac{8+1}{3}\right\rfloor=6 \end{align*} Since $8\equiv2\mod(3)$ we calculate \begin{align*} \color{blue}{a(8)}&=4\cdot 3\binom{4}{2}+2\left(4\binom{5}{1}-2\binom{4}{0}\right)\\ &=12\cdot 6 + 2\left(4\cdot 5 -2\right)\\ &=72+36\\ &\,\,\color{blue}{=108} \end{align*} in accordance with the blue marked value in the sequence (1). Note the binomial coefficient is set equal to $0$ if the lower index is negative.