17
$\begingroup$

Professor Erasmus has found a special way of moving a rook across a standard $8\times8$ chessboard that he modestly calls the "Professor-Erasmus-rook-tour". The professor claims that in this tour, the rook makes $64$ moves that visit all the $64$ squares of the chessboard. Every move is from some square to a horizontally or vertically adjacent square, and the very last move brings the rook finally back to its starting square. Exactly $32$ of these moves are in horizontal direction, and $32$ are in vertical direction.

Has the professor once again made one of his mathematical blunders, or do such rook tours indeed exist?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Since he claims to have found one (as opposed to presenting a non-constructive proof that one exists), I would ask him to demonstrate this tour. If he does so successfully, then such tours exist. If he fails, then he has made another blunder. (But other valud tours may still exist). $\endgroup$
    – KSmarts
    Commented Feb 3, 2015 at 18:09
  • 1
    $\begingroup$ When you say "to a horizontally or vertically adjacent square", do you indeed mean that the rook can move only one square orthogonally, rather that any number of spaces orthogonally as is usual for a chess rook? $\endgroup$
    – xnor
    Commented Feb 3, 2015 at 18:23

2 Answers 2

Reset to default
11
$\begingroup$

Update:

This problem can be simplified in the following way:

For an $n x n$ board where $n$ is even, make $\frac{n}{4}$ squares that are $2 x 2$.

This has $\frac{n^2}{2}$ horizontal and $\frac{n^2}{2}$ vertical moves.

Now, join any 2 adjacent shapes. When doing this, you will alter both the horizontal and vertical moves by 2.

Continue joining shapes until you have made 1 single shape taking up the entire board.

You can choose your adjustments so that for each join, you alternate between increasing and decreasing the horizontal moves.

To end up with a shape that has the same number of horizontal and vertical moves, it requires an even number of join operations, which requires an odd number of shapes.

Therefore, $\frac{n^2}{4}$ must be odd.

If $n = 8$ then $\frac{n^2}{4} = 16$. Because it is even, the number of join operations is odd, which means that you cannot end up with an identical number of horizontal and vertical moves.

So Professor Erasmus is incorrect. This cannot be done with an $8 x 8$ chessboard.

Original:

Professor Erasmus has made a mistake. He should have chosen a board with a side that is divisible by 2 but not 4.

2x2 board: Trivial to see that 4 moves must be 2 horizontal and 2 vertical.

4x4 board: Few enough paths to see that the best you can get is a difference of 4 between horizontal and vertical. Also, the worst you can get is a difference of 4.

6x6 board: Follow the outside edge for 17 moves, then zig-zag back through the center. Total of 18 horizontal, 18 vertical. This is one of many ways to achieve this.

8x8 board: Again, the best that you can do is a difference of 4 between horizontal and vertical.

I have not tried larger boards. I expect that my answer is accurate for them.

Improve this answer
$\endgroup$
9
  • $\begingroup$ What is the proof for the 8x8 board? $\endgroup$
    – Trenin
    Commented Feb 3, 2015 at 17:51
  • $\begingroup$ I do not have a full proof for the 8x8 board. Given what I tried with the 4x4 and then 6x6 board and the fact that similar answers didn't get me any closer than 4 for the 8x8, I believe it to be correct. I'll see if I can put something together later. $\endgroup$
    – Joel Rondeau
    Commented Feb 3, 2015 at 17:55
  • $\begingroup$ I'm in the same place as you. But, "I can't find one" doesn't mean, "there isn't one". I'm pretty sure there isn't, but I'm trying to prove it. $\endgroup$
    – KSmarts
    Commented Feb 3, 2015 at 18:06
  • 2
    $\begingroup$ Re your proof: not every possible rook tour can be made by joining 2x2 squares together, right? $\endgroup$
    – Lopsy
    Commented Feb 3, 2015 at 19:13
  • $\begingroup$ @Lopsy, I'm reasonably certain that every rook tour can be made this way for any $m x n$ board where $m$ and $n$ are both even. $\endgroup$
    – Joel Rondeau
    Commented Feb 3, 2015 at 19:22
1
$\begingroup$

Many tries, I always end up in 30 : 34. Is the start square important?

30

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I basically had the same problem :(... $\endgroup$
    – Valentin Grégoire
    Commented Feb 3, 2015 at 14:43
  • 1
    $\begingroup$ The start square shouldn't be important because he returns to it. Thus, there is a cycle, so any square in the cycle could be the start square. $\endgroup$
    – Trenin
    Commented Feb 3, 2015 at 16:17
  • $\begingroup$ I have no idea what this yellow and green board is supposed to represent. Where is the path? $\endgroup$
    – Florian F
    Commented Apr 23, 2022 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.