1
$\begingroup$

Two squares on a chessboard are said to be neighbours if they have an edge or a corner on the board in common. This means that squares on the edge have 5 neighbours, on the corner have 3 neigbours, and central squares have 8 neighbours.

A king moving normally on a chessboard always moves from a square to one of its neighbours.

Is it possible for a king to make a tour of a chessboard, visiting each square exactly once, in such a way that (apart from the square visited on the first move) every square that is visited has an even number of neighbours that have already been visted?

$\endgroup$
3
  • $\begingroup$ Could you, perhaps, give a small example to make the even condition clearer? $\endgroup$
    – Michael Burr
    Commented May 15, 2016 at 17:00
  • $\begingroup$ Starting from the end might be useful. The last move move has to be from an edge square to a central square. $\endgroup$
    – joriki
    Commented May 15, 2016 at 17:07
  • 2
    $\begingroup$ Do not vandalise your posts. $\endgroup$
    – Daniel Fischer
    Commented May 18, 2016 at 9:58

1 Answer 1

Reset to default
3
$\begingroup$

No. The total number of neighbourhood relations (or edges in the corresponding graph, if you prefer) is even. This follows without counting by observing what happens to horizontal, vertical, ascending diagonal, descending diagonal neighbourhoods upon rotating the board by 90 degrees. Thus in any tour visiting all squares, the number of steps where the number of previously visited neighbours is odd, must be even. As the first step is odd, the must be at least one other odd step.

$\endgroup$
1
  • $\begingroup$ @LucyJ: The rules imply that each step must add an even number to the number of pairs of neighbours that have been visited. There is an even number of such pairs to be completed, we start out with $0$ and the first step adds $1$, an odd number. To get to the even number in the end, some step needs to add an odd number. $\endgroup$
    – joriki
    Commented May 15, 2016 at 17:32

You must log in to answer this question.