King and knight moving on an infinite chess board 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.

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.
