Number of spaces a knight may reach within $n$ moves (chess)

176 Views Asked by At

So I got the idea to see if I could come up with a formula for the number of spaces a knight could reach on an infinitely large chess board within $n$ moves.

At first I was going to place the knight on an arbitrary square and attempt the problem recursively. However, I noticed that for $n\leqslant 3$, holes appeared in the interior of the spaces the knight could reach that posed an issue.

However, for $n\geqslant4$, these holes disappeared. I considered the following sequence and series:

$$r_n: \text{ number of spaces reached in a minimum of n moves}$$

$$s_n=\sum{r_n}$$

Here's a $10\times10$ board with values of $r_n$ given:

enter image description here

I removed the center of the board and split it into quadrants. I quickly calculated the following initial conditions:

$$r_0=1$$ $$r_1=8$$ $$r_2=32$$ $$r_3=68$$

I noted that for $n\geqslant 4$, $r_n=6n$ within a quadrant, meaning $r_n=4!\cdot n$ for the entire board. Using this, I figured that for $n\geqslant 4$, the following $s_n$ would give me the number of spaces a knight could reach within $n$ moves:

$$s_n=s_3+4!\sum_{k=4}^nk$$

$$s_n=109+4!\sum_{k=4}^nk$$

I then reexpressed as a quadratic:

$$s_n=12n^2+12n+103$$

I believe this is correct but could use some verification.

I also wanted to know how some more experienced discrete mathematicians would approach this problem


EDIT: I missed a space for $r_6$, meaning for $n\geqslant 6$, $r_n=28n-20$. After looking back, along the axes of the origin, the four spaces 11 units from the origin were also holes interor to a diagonal of 6s. Considering this, we proceed as earlier. Given that $r_4=96$ and $r_5=120$, we can write $s_n$ as follows:

$$s_n=s_5+4\sum_{k=6}^n[7k-5]$$

$$s_n=325+4\sum_{k=6}^n[7k-5]$$

As a quadratic:

$$s_n=98n^2-126n+350$$