[Math] King and knight moving on an infinite chess board

combinatoricsinfinite-games

There are actually two separate problems:

King problem:

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

enter image description here

Knight problem:

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

enter image description here

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

Best Answer

This is just illustration for what @Henning Makholm described:

(if somebody is interested in the implementation of this simulation, the code is here)

enter image description 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))$$.