17
$\begingroup$

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?

|cite|improve this question
$\endgroup$
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This is clearly wrong. If $m=n^2 - 1$, each square except one will always be occupied by a knight. Some knights will obviously threaten each other. I think you misunderstood the problem. $\endgroup$ – MathematicsStudent1122 Dec 31 '16 at 14:18
  • $\begingroup$ @MathematicsStudent1122 to be honest, Symlic answered the question in the exact way I interpreted it. You might want to reword your question a bit. I took "threaten each other" to mean that, if we label all of the knights $K_1, K_2, K_3,\dots ,K_n$ then we start by moving $K_1$, which is "threatening" the other knights if it has no square to move to that doesn't attack another knight. Once we move $K_1$ we then focus on $K_2$, then $K_3$, and so forth, looping back to $K_1$ after $K_n$ until a full tour is made by all Knights. Symlic's answers suffices under this interpretation. $\endgroup$ – Brevan Ellefsen Jan 3 '17 at 2:27
  • $\begingroup$ @BrevanEllefsen Threatening doesn't mean that each square a knight can move to is occupied. Only one. In other words, if we enumerate each position on the board $x_1, x_2, x_3..x_n$ there is no position such that two knights are in cells in which one can capture the other (e.g., a knight $K_j$ cannot be in a cell two to the right and one up from some other knight $K_i$). No, I won't reword it because $13$ other people aren't confused. Your interpretation is just wrong. I think this is straightforward. $\endgroup$ – MathematicsStudent1122 Jan 3 '17 at 2:46
  • $\begingroup$ @MathematicsStudent1122 OK. You can do what you want. Let it be noted however, that the only answer you have interpreted the question the way I did. Moreover, clarity is never a bad thing. Moreover, upvotes are not equivalent to mutual understanding of all parts of a question - they simply show an interest in seeing answers to said question (I have often seen posts upvoted with 10+ votes that did not deserve a single vote). That being said, my comment wasn't meant to attack you in any way... I meant it to help you get an answer. The more clear a question, the more likely an answer. $\endgroup$ – Brevan Ellefsen Jan 3 '17 at 2:50
  • $\begingroup$ Plus, editing a question puts it in the recent question feed and you would have an excuse to do that were you to add the details you put in your comment. I repeat what my point is though - (potential) redundancy for the purpose of clarity ought to be encouraged $\endgroup$ – Brevan Ellefsen Jan 3 '17 at 2:52
0
$\begingroup$

Only a partial hint/answer here, consider how many squares, attack how many others. In an N by N there are $(N-4)^2$ squares in which a knight can attack 8 squares (some of which are in that same block). there are a further $4N-4$ that attack 4 places, 4 that attack 2, and 4(N-4) that attack 6.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.