A variant of the Knight's tour problem

Question

The knight's tour problem is a famous problem in chess and computer science which asks the following question: can we move the knight on an $n \ \times \ n$ chessboard such that it visits every square exactly once? The answer is yes iff $n\geq5$. Additionally, there are algorithms which can solve it in $O(n^2)$ time.

I have two variations of it discussed below.

Fix an $n \ \times \ n$ chessboard. In this variant, instead of one knight we have $m$ knights. These knights take turns moving (ie., one knight moves, after that another one, once all of them have moved, the first one moves again and the cycle repeats itself).

What is the largest $m$ such that for some initial starting position, each knight can tour the board (as described in the first paragraph) without threatening any other knight? In other words, there is no "instance" of the chessboard in which one knight may capture another knight (e.g., knight $A$ cannot be, for example, two cells right and one cell up from another knight $B$ when it is his turn). Note that there is obviously an upper bound on $m$ (e.g., $n^2$).

In essence, I'm looking for a function $f:\mathbb{N}_{\geq 5} \to \mathbb{N}$ which assigns to each $n$ the largest possible $m$.

My second variation is exactly the same, except now there are no restrictions on the turns. After one knight moves, any knight can move, including the one that has moved prior. I do not know how these variations relate to each other; perhaps they are equivalent.

Also, as a function of $n$ what would the time complexity of an optimal algorithm be? Can either of these variants be solved in polynomial time?

Answer 1

For even $n$, $n \ge 6$, the answer is $m = n^2 - 1$ for both questions and the time is $O(n^2)$.

Obviously $m \le n^2 - 1$ is an upper bound, because at least one cell should be initially free. Let us see why it is reachable.

It is possible to construct a closed (cyclic) tour for one knight in the time of $O(n^2)$. The tour has additional property of symmetry, and the algo has property of good parallelization (i. e. it takes $O(1)$ on $n^2$ processors).

Let $C = v_1 v_2 \ldots v_n v_1$ be sequence of cells in such closed tour. Then we place the first knight into $v_n,$ the second one into $v_{n - 1}$, and so on, placing the last one, $m$th knight, into $v_2$. At the first turn the first knight moves to $v_1$, the second one moves to $v_n$, and so on, the last one moves to $v_3$. Then the first one moves to $v_2$ and so on and so on. Every knight walks through the entire tour.

For odd $n$ there is also a more tight upper bound: $m \le \frac{n^2 + 1}{2}$. It follows from a note that our graph is bipartite and has an odd order, so we should start every tour in the bigger part of graph (of $\frac{n^2 + 1}{2}$ cells). For the first question the upper bound is even less by $1$, because after the first turn all knights should be in the smaller part of graph (of $\frac{n^2 - 1}{2}$ cells).

May be some time later I'll investigate odd case more precisely.