13
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ See puzzling.stackexchange.com/questions/8511/the-erasmus-rook-tour $\endgroup$ – Barry Cipra Feb 7 '17 at 21:29
  • 2
    $\begingroup$ @BarryCipra That proof is incorrect, because it isn't proven that every path on a 8x8 board can be obtained by joining paths in 2x2 squares that way. $\endgroup$ – Wolfram Feb 7 '17 at 21:50
  • 1
    $\begingroup$ Come on, you have written that you're looking for hints, but now you opened the bounty with formulation "The current answers do not contain enough detail." Okay, I'll post the full solution, but why in the world is it necessary to downvote hints that you asked about or open the bounty instead of just asking to explain more in the comment? $\endgroup$ – Wolfram Feb 12 '17 at 18:25
  • $\begingroup$ You explicitly stated you don't know how to complete the proof. That's why the bounty. $\endgroup$ – VanDerWarden Feb 12 '17 at 18:27
  • $\begingroup$ Em, I said I don't know how to complete the proof from the link, but not how to complete the path I sketched in my answer, it is a bit different. Sorry if that was not clear. $\endgroup$ – Wolfram Feb 12 '17 at 18:34
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @VanDerWarden: Where has he? $\endgroup$ – Will R Feb 12 '17 at 20:50
  • $\begingroup$ @BenjiAltman of course they can move far away, but when you move a rook on the board, you usually slide it, so in some sense the fields on its path are still "visited". So the statement is a bit ambiguous. $\endgroup$ – Wolfram Feb 13 '17 at 17:21
  • $\begingroup$ @Wolfram If you define that way then this would work as a move order: Ra8, Rb8, Rb2, Rc2, Rc8, Rd8, Rd2, Re2, Re8, Rf8, Rf2, Rg2, Rg8, Rh8, Rh1, Ra1 $\endgroup$ – Benji Altman Feb 14 '17 at 2:52
  • $\begingroup$ Come on, only 14 horizontal moves, not 32. $\endgroup$ – Wolfram Feb 14 '17 at 8:02
  • 1
    $\begingroup$ @Wolfram Well, that is not the conventional meaning of "rook tour", so if that's what the OP means, then it's up to the OP to clarify the question. I don't think it's right to object to an answer that answers the question actually asked, based on an unverified guess that the intended question was something else. (But I see what you mean, and I think I agree with your guess that the intended question was indeed about adjacent square moves only.) $\endgroup$ – ShreevatsaR Feb 15 '17 at 17:23
3
+200
$\begingroup$

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: enter image description here Swap: enter image description here

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: enter image description here 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:

enter image description here

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ So is the proof from the link correct or not? $\endgroup$ – VanDerWarden Feb 8 '17 at 18:15
  • $\begingroup$ @VanDerWarden I don't see how to complete the proof from the link. $\endgroup$ – Wolfram Feb 8 '17 at 18:22
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The question asks for half of the moves to be vertical and half to be horizontal. $\endgroup$ – Nate Feb 16 '17 at 22:36
  • $\begingroup$ Ouch! Missed that. $\endgroup$ – Thumbnail Feb 16 '17 at 22:38

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.