2
$\begingroup$

If you have a $4 \times 4$ chessboard: Is it possible to make a Hamiltonian graph such that each step is like a move of the knight?

EDIT: But is an open knight tour? Thus possibly not an Hamiltonian cycle?

$\endgroup$
  • 1
    $\begingroup$ By the way it has been proved for which chessboards $m\times n$ do exist a tour. $\endgroup$ – Giovanni Resta Feb 13 '16 at 12:49
5
$\begingroup$

No. The only two squares that are connected to the top left square are also the only two squares that are connected to the bottom right square.

+---+---+---+---+
| A |   |   |   |
+---+---+---+---+
|   |   | Q |   |
+---+---+---+---+
|   | P |   |   |
+---+---+---+---+
|   |   |   | B |
+---+---+---+---+

Because the knight's tour needs to pass through A, both the moves AP and AQ must be taken (in some direction). Similarly, the knight need to pass through B, so both the moves BP and BQ must be taken in some direction.

But then we know two moves to/from P that the knight must make, and also two moves to/from Q that the knight must make. So it can't make any other moves that involve P or Q, and the cycle APBQ cannot be connected with the rest of a Hamiltonian path.

If you object that it only needs to be a Hamiltonian path, not necessarily a cycle, then conceivably the path could start or end at either A or B, such that this reasoning does not apply. But in that case the same thing would need to happen at the other diagonal, and this constrains the possible shapes enough that it is easily seen to be impossible to fit the middle of the path together correctly.

$\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.