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.

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