King and knight moving on an infinite chess board

Question

There are actually two separate problems:

King problem:

How many squares can a king moving on an infinite chess board reach in N moves?

Knight problem:

How many squares can a knight moving on an infinite chess board reach in N moves?

I solved the first one, but the second one seems much more difficult.

Answer 1

With the help of a computer (e.g. using Dijkstra's algorithm), try plotting the knight-reachable squares for, say, $N=10,11,12,13$. You should find that you get a solid octagon (whose diameter increases linearly with $N$), surrounded by a fuzzy fringe. But the width and pattern of the fuzzy fringe is the same for each $N$. If it were getting wider and more complex, the situation would be difficult to analyze, but here we have for each $N$:

• A solid octagon, with a number of squares that grows in proportion to the square of $N-k_1$ for some $k_1$.
• Eight corner patterns which are the same for each $N$, just displaced further out.
• Fuzzy fringes, consisting of a number of identical patterns that grows in proportion to $N-k_2$ for some $k_2$.

In sum, for large $N$, the number of reachable squares ought to grow as a second-degree polynomial. Fit such a polynomial to the values for $N=10,11,12$ and verify that it works for $N=13$ too.

For $N$s that are too small to allow the central solid octagon to develop, you will probably have to override the quadratic with tabulated values. But once $N$ gets large enough, the quadratic growth will continue indefinitely.

Answer 2

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))$$.