# How many squares can a limp queen move to?

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

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

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:

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

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:

• You can shift the central portion of the 8x8 path two steps to the right... Jan 19, 2022 at 10:02
• @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. Jan 19, 2022 at 13:34
• Also note that the question didn't specify that $n$ must be even; for odd numbers the gap is a bit different. Jan 20, 2022 at 5:09
• 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. Jan 20, 2022 at 12:24

The fruits of my labor:

Pears, I guess?

10 x 10 - 24 = 76
12 x 12 - 24 = 120

Extension to larger grids:

For all even $$n>10$$, path length $$n^2-2n$$

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$$

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.

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