4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Makholm, I truly wrote simulation of gradual reaching squares. No Dijkstra, just plain simulation using a regular array in Javascipt. $\endgroup$ – VividD Jan 6 '15 at 18:05
  • $\begingroup$ @VividD: Well, yes, anything smarter than enumerating all $n$-step sequences to see where each of them end... :) $\endgroup$ – Henning Makholm Jan 6 '15 at 18:12
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.