47
$\begingroup$

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.

Improve this question
$\endgroup$
13
  • 7
    $\begingroup$ Questions 2 and 4 are answered negatively by this demonstration, which decomposes the plane into concentric annuli of width two. $\endgroup$
    – Eric Towers
    Commented Mar 30, 2018 at 8:14
  • 1
    $\begingroup$ Here is an informal description of how to get a highly non-spiral (whatever that means) tour: In the subgroup generated by (1,2) and (2,-1), the knight can move like a king. This subgroup has index 5, so the quotient is cyclic. Now construct a tour as follows: cover some "big" area in the subgroup, then jump to the next coset, cover an "even bigger" area, and continue recursively. Not all "big areas" and not every way to cover them will work (e.g. you might block yourself from jumping back to the first coset after 5 iterations), but it is relatively easy to find some that do. $\endgroup$
    – Florian Lehner
    Commented Mar 30, 2018 at 11:55
  • 1
    $\begingroup$ My answer can also be used to make non-spiral tours, since you can assemble the $5\times 5$ blocks in any tiling, as long as each block is attached by a side to the next. It follows that there are continuum many such tours. $\endgroup$
    – Joel David Hamkins
    Commented Mar 30, 2018 at 12:05
  • 1
    $\begingroup$ @EricTowers I think you should post your comment as an answer! $\endgroup$
    – Joel David Hamkins
    Commented Mar 30, 2018 at 12:06
  • 1
    $\begingroup$ Another related question might be whether there exists a generalized chess piece which admits a Hamiltonian tour of $\mathbb{Z}^2$ but none that can be "reduced" to a king's tour. $\endgroup$
    – Gro-Tsen
    Commented Mar 30, 2018 at 14:52

3 Answers 3

Reset to default
58
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ (+1) Beautiful construction, Joel! I wonder if 5 is minimum $n$ in which one may carry out the spiral argument for an infinite knight's tour? $\endgroup$
    – Morteza Azad
    Commented Mar 30, 2018 at 1:00
  • 4
    $\begingroup$ Thanks! A $3\times 3$ board doesn't work since the middle square is unreachable, and I tried with $4\times 4$ for a while but didn't find anything that worked, so I moved on to $5\times 5$. At first I tried to start in the middle of a side, intending to have one "going straight" pattern and one "turning right" pattern, as you suggested, but then I realized that starting in a corner meant you could do both patterns at once. $\endgroup$
    – Joel David Hamkins
    Commented Mar 30, 2018 at 1:02
  • 3
    $\begingroup$ @paulgarrett Some people have looked at transfinite boards, with bishops, rooks and queens able to bridge the gap by following lines obeying their defining movements. I'm not sure, however, how much the result is like chess. For a knight's tour, one would want to define the limit ordinal time position of the knight on such a board, but this would seem difficult if the knight had been following the spiral pattern suggested in this answer, for example. Where would it be at time $\omega$? $\endgroup$
    – Joel David Hamkins
    Commented Mar 30, 2018 at 2:11
  • 5
    $\begingroup$ There is no $4\times 4$ Knight’s tour. For a proof, see Solution 3.4 of Across the Board: The Mathematics of Chessboard Problems by John J. Watkins. So 5 is indeed minimal. $\endgroup$
    – Robin Houston
    Commented Mar 30, 2018 at 12:34
  • 7
    $\begingroup$ Watkins also gives the following elegant argument: “Since you can remove four vertices from the knight’s graph of the $4\times 4$ chessboard and have the graph fall into six pieces, there could not possible have been a Hamiltonian path (you can’t make four cuts in a single length of string and end up with six pieces of string–well, most people can’t, maybe Ricky Jay could do it).” $\endgroup$
    – Robin Houston
    Commented Mar 30, 2018 at 12:37
25
$\begingroup$

(Moved from a comment.)

Questions 2, 3, and 4 are answered negatively by [W], which decomposes the plane into concentric annuli of width two.

Starting square plus the first two concentric annuli in the decomposition.

OP observes that this construction is still spiral (every move after the first rotates the direction vector from the origin to the knight clockwise). However, note that the move to transition from one ring to the next could be made so as to reverse the direction of the spiral. Instead of ending an annulus by moving (1,-2), the knight could move (2,-1) and fill the next annulus moving always counterclockwise. (Of course, the king could double-back the same way in its spiral tour.)

[W] Warendorff, Jay, "An Infinite Knight's Tour", the Wolfram Demonstrations Project, http://demonstrations.wolfram.com/AnInfiniteKnightsTour/ .

Improve this answer
$\endgroup$
4
  • $\begingroup$ (+1) Thanks for adding an expanded version of your informative comment as an answer, Eric! It perfectly completed the answer of my question! :-) $\endgroup$
    – Morteza Azad
    Commented Mar 30, 2018 at 14:32
  • $\begingroup$ @MortezaAzad : Glad to help! $\endgroup$
    – Eric Towers
    Commented Mar 30, 2018 at 14:58
  • 2
    $\begingroup$ Since the direction of each ring can be chosen independently, this method gives continuum many different knight's tours of the plane. $\endgroup$
    – Joel David Hamkins
    Commented Mar 30, 2018 at 18:22
  • $\begingroup$ @JoelDavidHamkins Classifying the knight's tours of the infinite plane as well as those infinite sub-spaces of the plane which admit a knight tour could be of some interest as well. However, I still have no particular natural notion of similarity/isomorphism for classifying the tours in mind. In some sense, a knight's tour could be considered a path/map in the plane. In this direction maybe some homotopy-like analysis provides interesting information. $\endgroup$
    – Morteza Azad
    Commented Mar 31, 2018 at 10:37
5
$\begingroup$

I've pictured the start of a more-or-less random-5-by-5 Hamkins-variant infinite Knight's tour construction. It begins at the center and proceeds to the SE corner of the 25-by-25 board.

Hamkins-variant infinite Knight's tour start

Improve this answer
$\endgroup$
1
  • $\begingroup$ Very nice, and convincing. Thank you for this beautiful illustration. $\endgroup$
    – André Henriques
    Commented May 12, 2019 at 17:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .