6
$\begingroup$

I was doing excercises about graphs theory and I came across a quite interesting excercise (which probably has something to do with Hamiltonian Cycle): "Is it possible to step on every field of a 4x4 or 5x5 chessboard just once and return to the starting point using a knight?" Does anyone have any idea how to tackle this problem? I am more interested in a outline of how to do it or just some hints.

$\endgroup$
  • 1
    $\begingroup$ This might be a good starting point: en.wikipedia.org/wiki/Knight's_tour $\endgroup$ – Adriano May 21 '13 at 22:22
  • 1
    $\begingroup$ You are correct that this can be viewed as a Hamiltonian Cycle problem. Make a graph whose vertex set is the set of squares on the chessboard and set vertex $u$ adjacent to $v$ if a knight can move from square $u$ to $v$. The problem is now to find a Hamiltonian cycle of this graph. $\endgroup$ – Austin Mohr May 21 '13 at 22:23
  • $\begingroup$ Recently on 9gag: 9gag.com/gag/aOqebpR $\endgroup$ – displayname Jan 7 '14 at 14:59
10
$\begingroup$

HINT:

$$\begin{array}{|c|c|c|c|} \hline \cdot&&&\\ \hline &&\cdot&\\ \hline &\cdot&&\\ \hline &&&\cdot\\ \hline \end{array}$$

$\endgroup$
  • $\begingroup$ If i start from the corner I have 2 possible moves, and I have 2 possible moves to get to the other corner. If my first move is to the lower square, then the only way i can get to the opposite corner is to do it now, but then the only available move would be to the upper square which is neccessary to get back to my starting point. This way i didnt visit all the fields. If from the lower square i would move in a different direction the only way i could get to the opposite corner is throught visiting the upper square first - which lefts my with no way to get back to the starting point. $\endgroup$ – Max May 21 '13 at 22:44
  • $\begingroup$ And i feel that you all wanted to show me that it is possible(which is true for a 4x4 chessboard and not for a 5x5 one, from what i've read on wikipedia) ;( (and i just proved that it's not if corners are the starting point) $\endgroup$ – Max May 21 '13 at 22:51
  • 1
    $\begingroup$ @Max: Since the goal is to return to the starting point, your path (if it exists) will be a Hamilton circuit, and it won’t matter where you start. Thus, if it’s impossible starting from a corner, it’s impossible, full stop. I would phrase the argument a bit differently, though. I’d note that the only way to go through the upper lefthand corner is to enter from one of the dotted cells in the middle and leave by the other. But the same is true of the lower righthand corner. Thus, if you go through both on a path that does not repeat any cell, you must be simply cycling through the four ... $\endgroup$ – Brian M. Scott May 21 '13 at 23:00
  • $\begingroup$ ... dotted cells, either clockwise or anti-clockwise. And that of course means that you’re not visiting any of the other $12$ cells. $\endgroup$ – Brian M. Scott May 21 '13 at 23:00
  • $\begingroup$ @Max: On Wikipedia there's an animated Knight's tour on a $5 \times 5$-board. $\endgroup$ – Martin May 21 '13 at 23:01
3
$\begingroup$

For the $5 \times 5$ chess board, we colour the squares black and white in a checkerboard fashion. There are $b:=\lfloor 5^2/2 \rfloor$ squares of one colour (say black) and $w:=\lceil 5^2/2 \rceil$ squares of the other colour (white).

Importantly, the knight moves are always black-to-white or white-to-black. Thus, for there to be a closed knight's tour, we would need the number $b=w$. However, $b<w$, so there is no closed knight's tour of this board.

$\endgroup$
2
$\begingroup$

Hint: You must enter and exit from each square. Look at the corners. What is special about them?

$\endgroup$
0
$\begingroup$

So I was skimming through the questions I've asked here and I remembered that I found a different solution to my question. Here it is:

If it is possible for a knight to step on every field of a chessboard, that means there is a Hamiltionian Cycle in a graph, in which a vertex is an equivalent to a square on the chessboard and the edges between vertices respond to the possibility of a move of a knight between the squares. There's a theorem that says if we remove a set V of k vertices in a Hamiltonian Graph then there are exactly k components of graph $G-V$. So if we remove four vertices in the middle we would get 4 isolated vertices and the rest of the graph - total of 5 components, which contradicts with the assumption that G was Hamiltonian.

$$\begin{array}{|c|c|c|c|} \hline \cdot&&&\cdot\\ \hline &\cdot&\cdot&\\ \hline &\cdot&\cdot&\\ \hline \cdot&&&\cdot\\ \hline \end{array}$$

$\endgroup$
  • $\begingroup$ I don't think you got that quite right. The theorem states that there will be at most $k$ components if you remove $k$ vertices from a Hamiltonian graph. Indeed, if we remove $k < n$ vertices from the complete graph $K_n$ (for some $n \geq 3$), we still only have one component, even though $K_n$ is clearly Hamiltonian. The proof you give still works, although you actually end up with 6 components, not 5. $\endgroup$ – Josse van Dobben de Bruyn Jul 23 '17 at 9:03

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.