Chess rook tour of 64 moves

Question

Consider an $8\times8$ chessboard. Let the rook be placed on the square a1. Is it possible for the rook to make a tour of $64$ moves such that:

• the rook visits every square once,
• the rook visits every square,
• the rook begins and ends on the square a1,
• the rook makes $32$ horizontal and $32$ vertical moves?

I'm looking for hints.

Clarification: if a rook makes a move from, say, a1 to a8, then squares a2 to a7 are considered visited as well.

Answer 1

I have found a solution that seems to fit what you are looking for.

$$ \begin{bmatrix} 58 & 61 & 62 & 57 & 25 & 26 & 13 & 14\\ 59 & 60 & 41 & 42 & 16 & 11 & 12 & 15\\ 33 & 34 & 21 & 22 & 9 & 10 & 29 & 30\\ 32 & 19 & 20 & 7 & 8 & 27 & 28 & 31\\ 46 & 18 & 5 & 6 & 17 & 45 & 38 & 37\\ 47 & 3 & 4 & 23 & 24 & 54 & 53 & 48\\ 1 & 2 & 40 & 43 & 50 & 44 & 39 & 49\\ 0 & 35 & 63 & 56 & 51 & 55 & 52 & 36 \end{bmatrix} $$

You may also notice that for all odd moves, the rook moves vertically, and for all even move the rook moves horizontally.

Edit: This solution no longer works as the clarification invalidates it.

Clarification: if a rook makes a move from, say, a1 to a8, then squares a2 to a7 are considered visited as well.

Answer 2

The idea from the link is correct. If we have some $2\times2$-subsquare with two parallel moves inside it (and no other moves inside it - remember about this), then we can change the two parallel moves into parallel moves in other direction and call it a swap. Here is a typical example: Swap:

One can prove that if we have some number of closed rook paths drawn on the board, then one swap always changes this number by 1 up or down, that is, changes parity. Indeed, let's think how the squares of the $2\times 2$ square where we make a swap can be connected from the the outside. WLOG, we can assume that swap changes 2 horizontal moves into 2 vertical. If the upper two squares are connected with each other from the outside, and the bottom two are connected from the outside, then we have two components affected under swap, and they become 1 component after the swap. If two right squares are connected and two left also, the situation is the opposite: we have 1 component with two red edges as in the picture before swap and 2 after the swap. There can never be a situation when upper left is connected with bottom right corner and upper right with bottom left. This is pretty obvious from the picture, but not so easy to prove formally: I'll add the details later, if you want.

Now let us prove that any path can be reduced to the union of the following 4 paths by a series of swaps: Why is this enough to disprove the existence of the path, described in the question? Obviously, we did an odd number of swaps, while reducing to this union of 4 paths, because each swap changed parity of the number of components, and initially there was the only one. However, this means that the number of swaps where we changed horizontal to vertical is not equal to the number of vice versa swaps. This means that we could not possibly preserve the property that the numbers of vertical and horizontal moves are the same, but in this union of 4 paths it is the same.

Now let us prove the main part: how we reduce any path to this union. We start to build firstly the outside layer, then after we done this, we can use similar method for inner $6\times 6$ square etc. Suppose in some moment the path along the border is not built: this means that there exist two neighbor squares at the border, not connected by a rook move:

Then we can swap two cyan edges and thus increase the number of edges along border by one. If we do this long enough, we eventually build the path along the border. However, there is an unpleasant case, where we can't do this:

If $A$ and $B$ are connected, we can't perform a swap. But if $C$ and $D$ are also connected, we can first make a swap in $ABCD$ square. Then $A$ and $B$ become disconnected, and we can swap two cyan moves. So the only bad case is when $C$ and $D$ are disconnected. Since they must be connected with two neighbor squares each, this means that the edges from them look like on the picture above. Then we can swap two orange edges and win... unless the two non-shown ends of the orange edges are also connected. Then move the picture two squares upper and repeat the argument until we hit the opposite side of the board. We obtain a structure where a lot of edges are known and there can be shown that this is impossible to continue it for covering the whole board by closed paths. I'll add technical details later.

Answer 3

Here's another solution based on the assumption that the rook only visits the square where it lands. (A "flying rook," so to speak...)

$$ M = \begin{bmatrix} 63 & 5 & 4 & 26 & 27 & 17 & 62 & 16 \\ 29 & 42 & 43 & 14 & 28 & 60 & 61 & 15 \\ 7 & 6 & 44 & 13 & 12 & 59 & 45 & 58 \\ 51 & 50 & 3 & 21 & 56 & 2 & 20 & 57 \\ 8 & 9 & 32 & 25 & 36 & 33 & 24 & 37 \\ 52 & 10 & 53 & 39 & 11 & 18 & 19 & 38 \\ 30 & 49 & 31 & 22 & 35 & 34 & 23 & 48 \\ 64 & 41 & 54 & 40 & 55 & 1 & 46 & 47 \end{bmatrix} $$ If $M_{i,j} = k$, then square $(i,j)$ is the destination of the $k$-th move. Square $(1,1)$, the starting position, is at the bottom-left corner. Compared to the presentation by @Benji, the only difference is that he labels $0$ what I label $64$.

This solution was generated by Z3. The constraints impose strict alternation between horizontal and vertical moves.

Answer 4

Unfortunately, the following is invalid. See comments.

---

Yes. A possible route is ...

a1 a8
h8 h7
b7 b6
h6 h5
b5 b4
h4 h3
b3 b2
h2 h1
a1

Half the moves in the above traverse many squares. To get exactly 64 of them, split the long moves into single steps. For example:

b6 h6 => b6 c6 d6 e6 f6 g6 h6

Since the route moves to every square once, there are 64 moves.