8
$\begingroup$

It is known that on an infinite board, if all squares of the form $(ki,kj)$ are removed, $k$ even, $i,j\in\mathbf{Z}$, then there is no knight's tour due to unbalanced black and white squares.

My questions are the following:

  1. If $k$ is odd, does there exist a knight's tour? For example, $k=3$.

  2. If finitely many black squares are to be removed, can there possibly exist a knight's tour?

Any results on these problems? Thanks.

Improve this question
$\endgroup$
1
  • $\begingroup$ There are cases where one can remove black squares to isolate one or more white squares. In those cases a tour is not possible. It is unclear to me (in the case of finitely many missing squares) if a tour is possible when every remaining square has a subtour through it. Gerhard "Maybe Compactness Can Be Used" Paseman, 2019.05.29. $\endgroup$
    – Gerhard Paseman
    Commented May 29, 2019 at 15:00

1 Answer 1

Reset to default
18
$\begingroup$

$k=3$ and $k=5$ are certainly possible, and I believe the procedure for $k=5$ can be extended to other odd $k$ as well. Here is a picture of $k=3$:


(click to enlarge; Java source code to generate this SVG file is here on GitHub)


(click to enlarge; Java source code to generate this SVG file is here on GitHub)

The procedure for $k=3$ is as follows: divide the board into 3-by-3 boxes, centered around the removed squares. There are eight ways for the knight to enter a box, and once it's in, it will make a complete tour in the box and end on one of the two other squares a knight's move away, so there are 16 possibilities labelled 0 through F:

enter image description here
(green = starting square, red = finishing square)

From one box, it can then jump to another box. The idea is to make a spiral of these boxes, centered at the origin. Therefore, we need to figure out for each box which other boxes can be next, depending on which direction we want to go. For example, from box 0 (and box D), we can't go left (we would end up in the box itself), we can go up to box A or B, down to box 2 or 3 and right to boxes 2, 3, A and B. The table is as follows:

enter image description here

Note that it's possible to go right by alternating between E and C, go down by F and 1, go left by 5 and 3 and go up by 9 and 7. This is the key to fill the spiral, which will look like this:

enter image description here
(For the first image, I ended up with C and F instead of 0 and 2 in the center.)

Since the length of the spiral's horizontal sides are always even, and odd for the vertical sides, this pattern can be extended indefinitely.

For $k \ge 5$, it makes more sense to leave the removed square in the corner. I had a computer program (linked above) brute-force all possible knights tours inside a $k$ by $k$ box with the top left square removed; then, it's a matter of finding the right 'connections' between the boxes like I did for the $k=3$ case.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great discovery and thanks a lot, Glorfindel! $\endgroup$
    – Haoran Chen
    Commented May 30, 2019 at 3:20

You must log in to answer this question.

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