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?

Question

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?

Answer 1

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.

Answer 2

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$

Answer 3

Not an answer, but too long for a comment.

Every third entry starting at the 2 in position 4 is https://oeis.org/A000984 , 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 .

Answer 4

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]) ;
    }
  }

Answer 5

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.