[Math] Does knight behave like a king in his infinite odyssey

chessco.combinatoricscombinatorial-game-theorygraph theoryinfinite-games

The Knight's Tour is a well-known mathematical chess problem. There is an extensive amount of research concerning this question in two/higher dimensional finite boards. Here, I would like to tackle this problem on the unbounded infinite board, $\mathbb{Z}\times\mathbb{Z}$.

The first issue is how to construct a knight's tour on the infinite plane. An intuitive way is to build it locally by mimicking the king's spiral tour in $\mathbb{Z}\times\mathbb{Z}$ board as follows:

enter image description here

Roughly speaking, a knight may follow the king's pattern by completing a knight's tour on an $n\times n$ block and then moving to the next block in the spiral order. For instance, in the below picture each square represents a certain $n\times n$ part of the $\mathbb{Z}\times\mathbb{Z}$ plane and the blue path is a knight tour performed in that particular block. It is connected to a point in the neighbor blocks with a knight move.

enter image description here

Of course, the existence of such a nice natural number $n$ should be checked. However, it sounds reasonable to expect that for a sufficiently large $n$ (which there are so many open knight tours with various beginning and ending points) there are some tours which can serve as the building blocks of the knight's king-like spiral. (Actually only a few straight and right-oriented $n\times n$ tours with appropriate beginning and ending points are needed. The other blocks will be redundant up to isomorphism).

Here, the first question arises:

Question 1. Is there (a concrete example of) a knight's tour on the infinite plane?

In the special case, does the already described strategy for building a knight's tour locally actually work? If yes, what is the minimum required $n$?

Assuming an affirmative answer to the above question, the next step is to speculate on the general structure of all possible knight tours on the infinite plane:

Question 2. Do all infinite knight's tours on the infinite plane arise as a combination of local finite knight's tours on a grid of blocks of the same size (whose local knight's tours are attached to their neighbor counterparts in a king's move fashion)?

Precisely, is it true that for any given knight's tour $t$ on the infinite plane $\mathbb{Z}\times\mathbb{Z}$, there is a (probably large) natural number $n$ and a partition $p$ of the plane into $n\times n$ blocks in a grid such that the restriction of $t$ into any block in $p$ is an $n\times n$ knight's tour in that particular block itself? We call the partition $p$ a localization of the knight's tour $t$ into a grid of $n\times n$ blocks.

If no, what is an example of an infinite knight's tour which can't be seen as a combination of local knight's tours in a grid of finite blocks of the same size (no matter what the resolution of the gird is)?

If yes, what is:
$$min\{n_t|~t~\text{is a knight's tour of $\mathbb{Z}\times\mathbb{Z}$ & there is a localization of}~t~\text{into a grid of}~n\times n~\text{blocks}\}$$
In better words, what is the finest possible resolution of a grid for a knight's tour of the infinite plane, $\mathbb{Z}\times\mathbb{Z}$?

As a remark it is worth mentioning that not all partitions of the infinite plane into $n\times n$ blocks are in the form of a perfect grid. For example, see the left picture in the following diagram which is a partition of the plane via $n\times n$ blocks different from a grid of $n\times n$ blocks (right):

enter image description here

So, for the sake of completeness, one may reduce the grid partition condition in question 2 to merely a partition of the infinite plane into $n\times n$ blocks:

Question 3. What is the answer to question 2 if we merely consider partitions of the infinite plane into $n\times n$ blocks, rather than those partitions which arrange blocks in a perfect grid?

The question could be asked in a more general sense as well:

Question 4. Is the knight's tour on the infinite plane always decomposable into finite knight's tours? Precisely, is it true that for every knight's tour $t$ on the infinite plane there is a partition $p$ of the plane into finite squares (not necessarily consisting of blocks in a grid or of the same size) such that the restriction of $t$ to any block in $p$ is a finite knight's tour as well?


Update. Thanks to Joel's answer and Eric's counterexample, the questions 1 and 2-4 have been answered positively and negatively respectively. Thus, we know that there are open knight's tours of the unbounded infinite plane, $\mathbb{Z}\times\mathbb{Z}$, of different nature, namely those which are formed of local knight's tours of finite planes and those total tours which don't arise this way. In this sense the answer to the question in the title is: "Sometimes but not always!"

Remark. As an additional piece of information, it is worth mentioning that there are some simple infinite sub-spaces of $\mathbb{Z}\times\mathbb{Z}$-plane which don't admit a knight's tour while some others do. For example, it is easy to see that one can obtain a knight's tour for $\mathbb{N}\times\mathbb{N}$ sub-plane through a local block by block construction via Joel's $5\times 5$ blocks introduced in his answer. However, it is intuitively clear that the infinite strip (i.e. $[-n,+n]\times\mathbb{Z}$ for some $n$) doesn't admit a knight's tour because the knight in such a sub-space must cover both infinite sides of the strip in a back and forth movement and so it should pass the central part of the strip infinitely many times which is impossible simply because after finitely many passages there will be no empty room left in the central region. Anyway, it sounds an interesting question to classify all infinite sub-spaces of $\mathbb{Z}\times\mathbb{Z}$-plane which admit a knight's tour. The same has already been done for all finite rectangle-shape sub-spaces of $\mathbb{Z}\times\mathbb{Z}$-plane, namely $m\times n$-boards.

Best Answer

Consider the following open knight's tour on a $5\times 5$ board, starting at position $1$ and then touring the $5\times 5$ board in the indicated move order. The final position is $25$, from which the knight can exit at either $A$ or $B$.

                         A

     5   22   17   12    7    B

    16   11    6   25   18

    21    4   23    8   13

    10   15    2   19   24

C    3   20    9   14    1

     D

So the tour starts at a corner, and can exit in either direction at an adjacent corner. By a suitable reflection of the same tour, we could also arrange to exit at C or D, if desired.

Therefore, with this pattern and its copies, we can proceed to tile any $5\times 5$ board and then arrange so as to enter any of the four adjacent $5\times 5$ boards on a corner as desired.

This allows us to tile any sequence of $5\times 5$ boards that are each connected to the next by a common edge. In particular, we can carry out your spiral pattern, since in that pattern each block has a common edge with the next block.

Thus, the answer is affirmative, there is a knight's tour of the infinite $\mathbb{Z}\times\mathbb{Z}$ chessboard.

Indeed, since this method allows one to follow any tiling of the plane by $5\times 5$ blocks, where each block is attached to a next block by an edge, it follows that there are continuum such knight's tours.

Related Question