8
$\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$?

Improve this question
$\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, 2022 at 6:53
  • $\begingroup$ Yes, since it turns 45 degrees (not 135). $\endgroup$
    – littlecat
    Jan 16, 2022 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, 2022 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, 2022 at 18:12
  • $\begingroup$ I think you should clarify that it's $\pm$45 degrees. In math, positive degrees denote anti-clockwise rotation. $\endgroup$
    – Acccumulation
    Jan 23, 2022 at 4:40

2 Answers 2

Reset to default
9
$\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

Improve this answer
$\endgroup$
4
  • $\begingroup$ You can shift the central portion of the 8x8 path two steps to the right... $\endgroup$
    – Daniel Mathias
    Jan 19, 2022 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$
    – Jaap Scherphuis
    Jan 19, 2022 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, 2022 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$
    – AxiomaticSystem
    Jan 20, 2022 at 12:24
5
$\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.

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

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.