1
$\begingroup$

I'm writing a small java program which calculates all possible knight's tours with the knight starting on a random field on a 5x5 board.

It works well, however, the program doesn't calculate any closed knight's tours which makes me wonder. Is there an error in the code, or are there simply no closed knight's tours on a 5x5 board?

If so, what is the minimum required board size for the existence of at least one closed knight's tour?

$\endgroup$
  • $\begingroup$ Could you please formally define a 'closed tour'? $\endgroup$ – Lelouch Mar 5 '17 at 12:46
  • 3
    $\begingroup$ There cannot be a closed knight's tour on a $5\times 5$ board, because the numbers of black and white squares have different parity. See also this question : math.stackexchange.com/questions/2010903/… $\endgroup$ – Arnaud D. Mar 5 '17 at 12:46
  • 1
    $\begingroup$ @Lelouch: It's a knight's tour, in which the knight returns on the starting position, i.e. like a loop $\endgroup$ – de_dust Mar 5 '17 at 12:48
  • 1
    $\begingroup$ The mathworld page mathworld.wolfram.com/KnightGraph.html on Knights tours contains an "iff" criterion for whether an $n \times n$ board has a closed knights tour. $\endgroup$ – Squid Mar 5 '17 at 12:49
4
$\begingroup$

No closed knight's tour is possible on a board with an odd number of squares, because each move changes the colour of the knight's square. So after an odd number of moves, you can't be back at the starting square, because it's the wrong colour.

$\endgroup$
  • $\begingroup$ As per the definition i read, a closed tour dosent refer to coming back to the starting square. See the wikipedia article: en.wikipedia.org/wiki/Knight's_tour $\endgroup$ – Lelouch Mar 5 '17 at 13:04
  • $\begingroup$ @Lelouch: The article you link to says: "If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed". Whether you consider the final move back to the beginning square to be part of the tour or not is a minor detail that doesn't change anything essential. $\endgroup$ – Henning Makholm Mar 5 '17 at 13:32
  • $\begingroup$ But supposing the starting square is black, for a board with an odd no. Of squares, every odd position, ie 1st, 3rd....mn th square will be black. There is no contradiction whatsoever is the last square being a different colour. Check the answer i mentioned below, notice that the last square is the same color as the starting square for an odd no. Of squares. $\endgroup$ – Lelouch Mar 5 '17 at 13:37
  • $\begingroup$ @Lelouch: Did you even read what I wrote? Whether you consider the final move back to the beginning square to be part of the tour or not is a minor detail that doesn't change anything essential. TonyKs argument considers a tour of $n^2$ moves that ends at the beginning square (which naturally has the same color as itself). You insist of considering a tour of $n^2-1$ moves that ends at a square where you could continue to move to the beginning square in one jump. What you consider to be the "final" square is the penultimate one of Tony's path; it must have the opposite color. $\endgroup$ – Henning Makholm Mar 5 '17 at 13:40
-1
$\begingroup$

The definition of a 'closed' knights tour on a $m \times n$board, is a sequence of steps from a starting square $a_1$ to another square $a_{mn}$ , such that every square is visited exactly once, and the last sqaure is only one knight step away from $a_1$. Having said that, it is obvious, that for $mn $(mod2) $= 1$, there exists no closed tour.

Short proof:

Suppose $a_1$ is black. Clearly then for any $i; i\le mn , i$(mod 2)$=1, a_i$ must be black. Since $mn$ is odd, $a_{mn}$ must be black, which implies that it cannot be a square one knight step away from $a_1$. Thus there exists no closed tour for odd $mn$.

$\endgroup$
  • $\begingroup$ The OP explicitly specified in a comment addressed to you well before you posted this answer: It's a knight's tour, in which the knight returns on the starting position. You're speaking about a different definition, where the knight stops short just a single move from returning to the starting position. Since your argument doesn't differ from the one in the already posted answer, except that you insist on phrasing it relative to a different definition that the one the OP explicit said he is working with, I don't really see what your point is. $\endgroup$ – Henning Makholm Mar 5 '17 at 13:46
  • $\begingroup$ Why do you even ask the OP for a definition if you're going to ignore it anyway and have the cheek to claim that the other answer is wrong simply because it does use the definition that the OP provided on your request? $\endgroup$ – Henning Makholm Mar 5 '17 at 13:47
  • $\begingroup$ I sincerely apologise for the inconvenience. I had read up the article before the OP had answered, and was halfway through my answer. I just realised that the previous answer is also correct. Sorry again. $\endgroup$ – Lelouch Mar 5 '17 at 13:50

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.