7
$\begingroup$

Consider a large chessboard. A limp rook is a chess piece that moves one step orthogonally, but it turns $90$ degrees after every move. The limp rook makes some moves, not crossing over its own path, and returning to the starting cell. It is known (see IMO Shortlist 2009 C6) that on an $n$ by $n$ grid, if $n$ is $3$ modulo $4$, the maximum number of steps the limp rook can take is $n^2-2n-3$.

A limp queen moves one step either orthogonally or diagonally, but it turns $45$ degrees instead (so changing its movement direction). How many cells can it visit in a cyclic path (not revisiting a square until the end) on an $n$ by $n$ grid if $n$ is $8$? $10$? How many for arbitrary $n$?

$\endgroup$
5
  • $\begingroup$ To clarify: must the queen be a knight’s move away from its starting position after its second move? $\endgroup$
    – dshin
    Jan 16 at 6:53
  • $\begingroup$ Yes, since it turns 45 degrees (not 135). $\endgroup$
    – littlecat
    Jan 16 at 18:07
  • $\begingroup$ May the limp queen choose at each step whether it's clockwise or anticlockwise? Is Qa1-b1-c2-c3-b4-b5 a legal move? $\endgroup$
    – Rosie F
    Jan 21 at 8:32
  • $\begingroup$ Of course the queen gets to decide what way to turn, else it can only make one path (an $8$-loop). $\endgroup$
    – littlecat
    Jan 21 at 18:12
  • $\begingroup$ I think you should clarify that it's $\pm$45 degrees. In math, positive degrees denote anti-clockwise rotation. $\endgroup$ Jan 23 at 4:40

2 Answers 2

8
$\begingroup$

To kick this thing off, I've got:

32 (50%) moves on an 8x8, but 68 (68%) moves on the 10x10 and a very nice 108 (75%) on the 12x12 illustrating a parity-swap mechanism:
enter image description here

EDIT: I've come across useful patterns that provide good answers for even $n$ greater than 6:

enter image description here
The 4k+2 case is fairly straightforward: the dense section connects the outer strands to the inner strands, and the looser bottom connects the outer strands to each other (and likewise the inner strands).
The 4k case looks more complicated, but it reduces to choosing an appropriate k-by-k system of loops, and finding a corresponding k-by-(k-1) to fill in the middle. If you've chosen your pair wisely, you can take a pair of loops and twist them together, merging the two loops into a single path as shown here: enter image description here

Imgur Link

$\endgroup$
4
  • $\begingroup$ You can shift the central portion of the 8x8 path two steps to the right... $\endgroup$ Jan 19 at 10:02
  • $\begingroup$ @DanielMathias Yes, but how could that shifted part connect with the rest while maintaining the 45 degree turn rule? Edit: Wait, I think you're right and it is possible if you cross the two ends over. $\endgroup$ Jan 19 at 13:34
  • $\begingroup$ Also note that the question didn't specify that $n$ must be even; for odd numbers the gap is a bit different. $\endgroup$
    – littlecat
    Jan 20 at 5:09
  • $\begingroup$ I noticed that, and investigated odd grids for a bit after posting the edit, but didn't see any meaningful way to improve upon the shown patterns. $\endgroup$ Jan 20 at 12:24
4
$\begingroup$

The fruits of my labor:

Pears, I guess?
enter image description here
10 x 10 - 24 = 76
12 x 12 - 24 = 120

Extension to larger grids:

For all even $n>10$, path length $n^2-2n$
enter image description here

Improvement, possibly optimal:

For all even $n>8$, path length $n^2-24$
Shown above: $n=10$ and $n=12$
Shown here: $n=14$ and $n=16$
enter image description here
Possibly optimal: $n^2-20$ would be optimal (minimum: 5 unvisited cells near each corner), but I have been unable to find such a path.

$\endgroup$
2
  • $\begingroup$ Can you prove $n^2-2n$ is optimal? $\endgroup$
    – littlecat
    Jan 21 at 2:49
  • 3
    $\begingroup$ @littlecat I can prove that it isn't. $\endgroup$ Jan 23 at 3:34

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.