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?