Color the cells with four colors as follows. 4 2 4 2 4 2 ... 3 1 3 1 3 1 ... 4 2 4 2 4 2 ... 3 1 3 1 3 1 ... ... The order of the colors in the cycle must be either 1,3,4,2,1,3,4,2,... or 1,2,4,3,1,2,4,3,... The number of cells of each color in the cycle must be equal. There are $499^2$ cells of color 1. We will prove that not all cells of color 1 can be visited, then the upper bound will be $4(499^2-1)$. Assume all cells of color 1 are visited, call them "good cells". Color them with black and white. Since the number of cells is odd, then at some point the rook will move from a good cell to another good cell of the same color. Suppose the route is $(a,b)\rightarrow(a,b+1)\rightarrow(a+1,b+1)\rightarrow(a+1,b+2)\rightarrow(a+2,b+2)$ where the colors are 1,2,4,3,1 respectively. Consider the cell $(a,b+2)$. The rook must pass through $(a-1,b+2)\rightarrow(a,b+2)\rightarrow(a,b+3)$ because we must go to color 2 from color 1. Now we have to connect $(a,b+3)$ with $(a,b)$ and also $(a+2,b+2)$ with $(a-1,b+2)$. It is easy to see that the two paths will intersect, a contradiction. The construction is not difficult. Try with small $n\equiv3\pmod4$, then construct inductively.

The solution above with the good coloring is very smart. Here's another proof, less smart and longer but using only straightforward observations. First, one can see that it's impossible to start or go through corners. Indeed, a few tries show trivially that the only valid path from a corner is a path of lenght 4 (the most little cycle) and that we can do (way) better... Assume in a first place that the maximum path start from the leftmost edge.Therefore, we'll show for $n$ odd the maximum path has a lenght of at most $n^2-2n-3$. To see so, observe that each column must have an odd number of non-visited cells. Indeed, if one go through a column, he must go back to close the cycle and then visit an even number of cells on a column. But a column has an odd number of cells, then you must leave an odd number of non visited cells. Obviously, the same is true for lines. Therefore, each column and each line has at least one non-visited cell. Moreover, consider a column and define $c_i$ the i-th case, counted from bottom. For instance, the first cell from bottom is $c_1$. Observe that a move in a column must visit exaxctly 2 adjacent cases before going out of the column. Then, if $c_i$ is the unvisited cell on this column and $i$ is even, there must be at least 2 other unvisited cells. Indeed, if $i$ is even, then the column is split into two columns with each an odd lenght. But each line of height $i$("height" is the number of the line, counted from bottom), with $i$ even, must have an unvisited cell. Therefore, for every one of them, one can associate 2 other unvisited cells on a column. So, if we focus only on columns to count, and recalling that the 4 corners can't be visited independantly with the remarks above, we have at least $3 \frac{n-1}{2} + \frac{n+1}{2}+4 = 2n+3$ unvisited cells. ( $\frac{n-1}{2}$ is the number of even numbers from 1 to n, and $\frac{n+1}{2}$ the number of odd numbers) In the beginning, we've assumed that we start on the edge. Observe that if we start on another cell visitng at any moment an edge,then we can rewrite the path starting on the edge. The only case where it's impossible is if we never go on an edge. Hopefully, the best we can do is $(n-2)^2$ (visiting all cells); which is less than what we've just found. Therefore one can visit at most $n^2 - 2n-3$ , that is in the problem 996000 cases. The construction is not as trivial as claimed by the previous post. I'll give one later.

The answer is $996000$. We prove the answer for an $n\times n$ board, with $n\equiv3\pmod4$ and $n\ge7$, is $n^2-2n-3$. Proof of lower bound. We first show $n^2-2n-3$ is achievable. Shown below is a construction for $n=15$: [asy][asy] size(7cm); defaultpen(fontsize(10pt)); fill( (.5,.5)--(15.5,.5)--(15.5,15.5)--(.5,15.5)--cycle,pink+white+white); fill( (4.5,8.5)--(7.5,8.5)--(7.5,11.5)--(4.5,11.5)--cycle,purple+white+white); fill( (.5,3.5)--(1.5,3.5)--(1.5,5.5)--(.5,5.5)--cycle,purple+white+white); fill( (.5,.5)--(1.5,.5)--(1.5,1.5)--(.5,1.5)--cycle,purple+white+white); fill( (13.5,.5)--(15.5,.5)--(15.5,2.5)--(14.5,2.5)--(14.5,1.5)--(13.5,1.5)--cycle,purple+white+white); fill( (12.5,2.5)--(13.5,2.5)--(13.5,3.5)--(12.5,3.5)--cycle,purple+white+white); fill( (14.5,14.5)--(14.5,15.5)--(15.5,15.5)--(15.5,14.5)--cycle,purple+white+white); fill( (11.5,12.5)--(12.5,12.5)--(12.5,11.5)--(13.5,11.5)--(13.5,13.5)--(11.5,13.5)--cycle,purple+white+white); fill(reflect( (0,0),(1,1))*( (13.5,.5)--(15.5,.5)--(15.5,2.5)--(14.5,2.5)--(14.5,1.5)--(13.5,1.5)--cycle),purple+white+white); fill(reflect( (0,0),(1,1))*( (12.5,2.5)--(13.5,2.5)--(13.5,3.5)--(12.5,3.5)--cycle),purple+white+white); fill( (2.5,6.5)--(4.5,6.5)--(4.5,7.5)--(3.5,7.5)--(3.5,8.5)--(2.5,8.5)--cycle,purple+white+white); fill(shift(-4,4)*( (13.5,.5)--(15.5,.5)--(15.5,2.5)--(14.5,2.5)--(14.5,1.5)--(13.5,1.5)--cycle),purple+white+white); fill(shift(-4,4)*( (12.5,2.5)--(13.5,2.5)--(13.5,3.5)--(12.5,3.5)--cycle),purple+white+white); fill( (10.5,10.5)--(11.5,10.5)--(11.5,11.5)--(10.5,11.5)--cycle,purple+white+white); fill( (7.5,10.5)--(8.5,10.5)--(8.5,11.5)--(7.5,11.5)--cycle,purple+white+white); for (real i = 1; i <= 14+1e-9; i += 1) { draw( (i+.5,.5)--(i+.5,15.5),gray); draw( (.5,i+.5)--(15.5,i+.5),gray); } draw( (.5,.5)--(15.5,.5)--(15.5,15.5)--(.5,15.5)--cycle,linewidth(1)); draw( (1,2)--(2,2)--(2,1)--(3,1)--(3,2)--(4,2)--(4,1)--(5,1)--(5,2)--(6,2)--(6,1)--(7,1)--(7,2)--(8,2)--(8,1)--(9,1)--(9,2)--(10,2)--(10,1)--(11,1)--(11,2)--(12,2)--(12,1)--(13,1)--(13,2)--(14,2)--(14,3)--(15,3)--(15,4)--(14,4)--(14,5)--(15,5)--(15,6)--(14,6)--(14,7)--(15,7)--(15,8)--(14,8)--(14,9)--(15,9)--(15,10)--(14,10)--(14,11)--(15,11)--(15,12)--(14,12)--(14,13)--(15,13)--(15,14)--(14,14)--(14,15)--(13,15)--(13,14)--(12,14)--(12,15)--(11,15)--(11,14)--(10,14)--(10,15)--(9,15)--(9,14)--(8,14)--(8,15)--(7,15)--(7,14)--(6,14)--(6,15)--(5,15)--(5,14)--(4,14)--(4,15)--(3,15)--(3,14)--(2,14)--(2,13)--(1,13)--(1,12)--(2,12)--(2,11)--(1,11)--(1,10)--(2,10)--(2,9)--(1,9)--(1,8)--(2,8)--(2,7)--(1,7)--(1,6)--(2,6)--(2,5)--(3,5)--(3,6)--(4,6)--(4,5)--(5,5)--(5,6)--(6,6)--(6,5)--(7,5)--(7,6)--(8,6)--(8,5)--(9,5)--(9,6)--(10,6)--(10,7)--(11,7)--(11,8)--(10,8)--(10,9)--(11,9)--(11,10)--(10,10)--(10,11)--(9,11)--(9,10)--(8,10)--(8,9)--(9,9)--(9,8)--(8,8)--(8,7)--(7,7)--(7,8)--(6,8)--(6,7)--(5,7)--(5,8)--(4,8)--(4,9)--(3,9)--(3,10)--(4,10)--(4,11)--(3,11)--(3,12)--(4,12)--(4,13)--(5,13)--(5,12)--(6,12)--(6,13)--(7,13)--(7,12)--(8,12)--(8,13)--(9,13)--(9,12)--(10,12)--(10,13)--(11,13)--(11,12)--(12,12)--(12,11)--(13,11)--(13,10)--(12,10)--(12,9)--(13,9)--(13,8)--(12,8)--(12,7)--(13,7)--(13,6)--(12,6)--(12,5)--(13,5)--(13,4)--(12,4)--(12,3)--(11,3)--(11,4)--(10,4)--(10,3)--(9,3)--(9,4)--(8,4)--(8,3)--(7,3)--(7,4)--(6,4)--(6,3)--(5,3)--(5,4)--(4,4)--(4,3)--(3,3)--(3,4)--(2,4)--(2,3)--(1,3)--cycle); draw( (.5,4.5)--(11.5,4.5)--(11.5,11.5)--(4.5,11.5)--(4.5,8.5)--(7.5,8.5)--(7.5,11.5),linewidth(1)); [/asy][/asy] The route of the limp rook forms a ``snake'' that coils around the board, leaving only a $3\times3$ square unfilled. Furthermore the two ends of the snake each leave $2$ squares unfilled, and each turn of the snake leaves $4$ squares unfilled. This construction leaves a total of $2n+3$ squares unfilled, as desired. Proof of upper bound. We prove $n^2-2n-3$ is maximal. Color the squares in the grid as follows: [asy][asy] size(3.5cm); defaultpen(fontsize(10pt)); for (real i = 0; i <= 6+1e-9; i += 2) for (real j = 0; j <= 6+1e-9; j += 2) { fill( (i,j)--(i,j+1)--(i+1,j+1)--(i+1,j)--cycle,lightred+white); } for (real i = 1; i <= 6+1e-9; i += 2) for (real j = 0; j <= 6+1e-9; j += 2) { fill( (i,j)--(i,j+1)--(i+1,j+1)--(i+1,j)--cycle,lightyellow+white); } for (real i = 0; i <= 6+1e-9; i += 2) for (real j = 1; j <= 6+1e-9; j += 2) { fill( (i,j)--(i,j+1)--(i+1,j+1)--(i+1,j)--cycle,lightgreen+white); } for (real i = 1; i <= 6+1e-9; i += 2) for (real j = 1; j <= 6+1e-9; j += 2) { fill( (i,j)--(i,j+1)--(i+1,j+1)--(i+1,j)--cycle,lightblue+white); } for (real i = 1; i <= 6+1e-9; i += 1) { draw( (i,0)--(i,7),gray); draw( (0,i)--(7,i),gray); } draw( (0,0)--(0,7)--(7,7)--(7,0)--cycle); [/asy][/asy] Let $R$ denote the color red, and so on. The sequence of colors on the route of the limp rook must repeat in the pattern \[R,\ Y,\ B,\ G,\ R,\ Y,\ B,\ G,\ \ldots\](or the above sequence reversed). It follows that the length of the sequence is $4T$, where $T$ is the number of blue squares on the limp rook's route. Claim: The limp rook cannot pass through all the blue squares. Proof. Assume for contradiction the limp rook passes through all the blue squares. Say two blue squares are consecutive if the limp rook visits them without visiting any other blue square in between. Note that two consecutive blue squares must be either orthogonally adjacent or diagonally adjacent. Checkerboard color the blue squares periwinkle and navy blue. Since there is an odd number of blue squares, the number of periwinkle squares and the number of navy blue squares are unequal. Thus there is at least one pair of diagonally adjacent consecutive blue squares. [asy][asy] size(3cm); defaultpen(fontsize(10pt)); for (real i = 0; i <= 4+1e-9; i += 2) for (real j = i % 4; j <= 4+1e-9; j += 4) { filldraw( (i,j)--(i,j+1)--(i+1,j+1)--(i+1,j)--cycle,lightblue+white,gray); } for (real i = 0; i <= 4+1e-9; i += 2) for (real j = (i+2) % 4; j <= 4+1e-9; j += 4) { filldraw( (i,j)--(i,j+1)--(i+1,j+1)--(i+1,j)--cycle,lightcyan+white,gray); } draw( (.5,2.5)--(1.4,2.5),Arrow()); draw( (1.5,2.4)--(1.5,1.6),Arrow()); draw( (1.6,1.5)--(2.4,1.5),Arrow()); draw( (2.5,1.4)--(2.5,0.5),Arrow()); draw( (2.5,3.5)--(2.5,2.6),Arrow()); draw( (2.6,2.5)--(3.5,2.5),Arrow()); [/asy][/asy] Without loss of generality the limp rook moves \[(a,b+2)\to(a+1,b+2)\to(a+1,b+1)\to(a+2,b+1)\to(a+2,b).\]Then since the limp rook must move in the pattern $R$, $Y$, $B$, $G$, $\ldots$, at some point in the sequence the limp rook moves $(a+2,b+3)\to(a+2,b+2)\to(a+3,b+2)$. Then the rook must eventually move from $(a+2,b)$ to $(a+2,b+3)$ and $(a+3,b+2)$ to $(a,b+2)$. It is clear these two paths must intersect, contradiction. $\blacksquare$ Hence the length of the limp rook's route is at most \[4\left[\left(\frac{n-1}2\right)^2-1\right]=n^2-2n-3,\]and we are done.

Solution from Twitch Solves ISL: The answer is $4 \cdot (499^2-1)$. First consider the following coloring of the board: \[ \begin{array}{|ccccc} \hline A & B & A & B & \dots \\ D & C & D & C & \dots \\ A & B & A & B & \dots \\ D & C & D & C & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array} \]A limp rook must move $A \to B \to C \to D \to A \to \dots$ (or backwards, but then just reverse the path) so an immediate upper bound is given by four times the number of $C$'s, which is equal to $4 \cdot 499^2$. We will improve this bound slightly. Claim: The path of the limp rook cannot move between non-orthogonally adjacent letter $C$'s. Proof. Assume not. Since $C$ appears every four moves, the limp rook must have reached a diagonally adjacent $C$. We illustrate the situation below, with cells denoted by points rather than squares. Consider the $C$ which is wrapped around by the path (see illustration). The path reaches this $C$ eventually to, and most do so via $B \to C \to D$ as shown. [asy][asy] size(9cm); draw( (0,2)--(1,2), red, EndArrow, Margins); draw( (1,2)--(1,1), red, EndArrow, Margins); draw( (1,1)--(2,1), red, EndArrow, Margins); draw( (2,1)--(2,0), red, EndArrow, Margins); draw( (2,3)--(2,2), deepcyan, EndArrow, Margins); draw( (2,2)--(3,2), deepcyan, EndArrow, Margins); draw( (3,2)..(1.5,-1)..(0,2), grey+dashed, EndArrow, Margins); draw( (2,0)..(4,1.5)..(2,3), grey+dashed, EndArrow, Margins); dot("$C$", (0,2), dir(45), red); dot("$D$", (1,2), dir(45), red); dot("$A$", (1,1), dir(45), red); dot("$B$", (2,1), dir(45), red); dot("$C$", (2,0), dir(45), red); dot("$B$", (0,1), dir(45)); dot("$C$", (0,0), dir(45)); dot("$D$", (1,0), dir(45)); dot("$B$", (2,3), dir(135), deepcyan); dot("$C$", (2,2), dir(225), deepcyan); dot("$D$", (3,2), dir(90), deepcyan); [/asy][/asy] However, we now see there is no non-intersecting way that we could unite these two paths (grey paths must intersection), which gives a contradiction. $\blacksquare$ Because of this, the number of $C$'s used must be even, so we have a bound of $4 \cdot (499^2-1)$ now. The construction is achieved by a ``spiral path'' we illustrate below, here for a $15 \times 15$ grid but which can be generalized readily. [asy][asy] size(14cm); pair P = (0,12); // current pointer for (int i=-1; i<14; ++i) { for (int j=-1; j<14; ++j) { dot((i,j), rgb(0.8,0.8,0.8)); } } pen rook = red; path wiggle = (0,0)--(1,0)--(1,1)--(2,1)--(2,0); path squiggle = (0,0)--(0,1)--(1,1)--(1,0)--(2,0); for (int i=0; i<6; ++i) { draw(shift(P) * wiggle, rook); P += (2,0); } for (int i=0; i<6; ++i) { draw(shift(P) * rotate(-90) * squiggle, rook); P += (0, -2); } for (int i=0; i<6; ++i) { draw(shift(P) * rotate(180) * wiggle, rook); P += (-2, 0); } draw(shift(P) * rotate(90) * squiggle, rook); P += (0,2); for (int i=0; i<5; ++i) { draw(shift(P) * yscale(-1) * wiggle, rook); P += (2, 0); } for (int i=0; i<4; ++i) { draw(shift(P) * yscale(-1) * rotate(-90) * squiggle, rook); P += (0, 2); } for (int i=0; i<4; ++i) { draw(shift(P) * xscale(-1) * wiggle, rook); P += (-2, 0); } for (int i=0; i<2; ++i) { draw(shift(P) * xscale(-1) * rotate(-90) * squiggle, rook); P += (0, -2); } for (int i=0; i<2; ++i) { draw(shift(P) * yscale(-1) * wiggle, rook); P += (2, 0); } draw(shift(P) * yscale(-1) * rotate(-90) * squiggle, rook); P += (0,2); draw(shift(P) * wiggle, rook); P += (2,0); for (int i=0; i<2; ++i) { draw(shift(P) * rotate(-90) * squiggle, rook); P += (0, -2); } for (int i=0; i<4; ++i) { draw(shift(P) * rotate(180) * wiggle, rook); P += (-2, 0); } for (int i=0; i<4; ++i) { draw(shift(P) * rotate(90) * squiggle, red); P += (0, 2); } for (int i=0; i<7; ++i) { for (int j=0; j<7; ++j) { dot("$C$", (2*i,2*j), dir(45), blue); } } [/asy][/asy]

The answer is $4(499^2-1)$. Consider labeling the rows and columns from $1$ to $999$; color the square $(i,j)$ with $1$ if $i,j$ are odd, with $2$ if $i$ odd, $j$ even, with $3$ if $i$ odd, $j$ even, and $4$ if $i,j$ even. Observe that any cycle of the limp rook will go through colors $1,2,3,4$ in that order. Therefore, the number of squares that the rook visits is $4$ times the number of $4$s it passes through. Observe that there are $499^2$ $4$s, in a grid-like pattern that are $2$ spaces apart. I claim that we can not go through every single $4$. Assume for the sake of contradiction that we could. From any $4$, it can go to either an adjacent one on the same row/column or a $4$ that's diagonally across (every $4$ moves must contain exactly one $4$). Define an "adjacent move" as one that moves to an adjacent square, and a diagonal move otherwise. Consider a chessboard coloring of black and white on the $4$s. It's obvious that there must be an odd number of diagonal moves. If we go around this path in one direction, then denote the direction of a square as whether the path goes into the square horizontally or vertically. If a black square's direction is horizontal, then every black square's direction will be horizontal until we reach a diagonal, which switches the direction of black squares. However, since there are an odd number of diagonal moves, the direction of square $A$ will be different from the direction of square $A$ once we go around the entire path, a contradiction. Therefore, we can never pass $499^2$ $4$s. Now, for the construction. Consider going from the bottom left $4$, and going all the way across the row. Then, move up to the next row, and go all the way across to the 2nd element of that row. Keep doing this (so going from the 2nd element to the last and vice versa per row), until you reach the $2nd$ to last row. Now, we can alternate going across $1$ then up $1$, then across $1$, then down $1$, until we reach the first column. Go down to the bottom left element to complete the cycle. Therefore $4(499^2-1)$ is our answer. Here's a picture (for $5$ by $5$ grids of $4$s because I can't draw or something)

Color the squares as follows: color the top left square red, the one directly to the right of that blue, the one directly below blue as green, and the one directly to the left of green as yellow. Note that any four squares that a limp rook adjacently visits must be one of each color, so if the rook visits $k$ green squares then the limp rook visited $4k$ total squares. It suffices to maximize $k$. Clearly, $k\le 499^2$ since that's the number of green squares. In fact, we will prove one less, that the limp rook cannot visit every green square. Suppose otherwise. Then color the green squares as dark green or light green, like on chess.com, with dark green on the corners. Note that there is one more dark green than light green, so at some point, the limp rook goes from dark green to dark green after four moves. Clearly, after four moves the rook does not exceed more than two units from its original position horizontally or vertically. Thus, let a moooove be a four-move sequence that takes one green square to another green square. Let a good moooove be a four-move sequence that takes a green square to a differently shaded green square, either vertically or horizontally, and let a bad moooove be a four-move sequence that takes a green square to a similarly shaded green square, diagonally. There are $499^2$ mooooves and an odd number of which are bad. Note that the good moooove stays going in one direction until a bad moooove is reached, which changes the direction. Pick any good moooove, which clearly must exist, and the direction going in must be same as the direction going out, so there are even number of bad mooooves, contradiction. Construction for $k=499^2-1$ is omitted.

Another construction since why not. Note that we can partition the $499 \times 499$ center pieces into $k \times k$ "frame" using at most thickness $2$ for $k = 3, 5, \dots 499$. Then this $499 \times 499$ grid is a $1 \times 1$ plus a bunch of frames. There's actually two ways to place the frames, so take it such that adjacent frames have different "parities" at the corners. We can connect the purple $k \times k$ and $(k + 2) \times (k + 1)$ frames together as seen below using the magenta connectors. Repeat this for each frame at different corners each time to finish. [asy][asy] size(10cm); int N = 11; for (int i = 0; i <= N; ++i) { draw((0,i)--(N,i)); draw((i,0)--(i,N)); } for (int i = 0; i <= N/2 - 1; ++i) { for (int j = 0; j <= N/2 - 1; ++j) { fill(shift(1+2*i,1+2*j)*unitsquare, red+white+white); } } path p1 = (1,1)--(0,1)--(0,2)--(1,2)-- (1,3)--(0,3)--(0,4)--(1,4)-- (1,5)--(0,5)--(0,6)--(1,6)-- (1,7)--(0,7)--(0,8)--(1,8)-- (1,9)--(2,9)--(2,10)--(3,10)-- (3,9)--(4,9)--(4,10)--(5,10)-- (5,9)--(6,9)--(6,10)--(7,10)-- (7,9)--(8,9)--(8,10)--(9,10)-- (9,9)--(10,9)--(10,8)--(9,8)-- (9,7)--(10,7)--(10,6)--(9,6)-- (9,5)--(10,5)--(10,4)--(9,4)-- (9,3)--(10,3)--(10,2)--(9,2)-- (9,1)--(8,1)--(8,0)--(7,0)-- (7,1)--(6,1)--(6,0)--(5,0)-- (5,1)--(4,1)--(4,0)--(3,0)-- (3,1)--(2,1)--(2,0)--(1,0)--cycle; path p2 = (3,3)--(3,4)--(2,4)--(2,5)-- (3,5)--(3,6)--(2,6)--(2,7)-- (3,7)--(3,8)--(4,8)--(4,7)-- (5,7)--(5,8)--(6,8)--(6,7)-- (7,7)--(7,6)--(8,6)--(8,5)-- (7,5)--(7,4)--(8,4)--(8,3)-- (7,3)--(7,2)--(6,2)--(6,3)-- (5,3)--(5,2)--(4,2)--(4,3)-- cycle; draw(shift(0.5,0.5)*p1, purple+linewidth(1)); draw(shift(0.5,0.5)*p2, purple+linewidth(1)); path a1 = (7,7)--(7,8)--(8,8)--(8,7)--(9,7); draw(shift(0.5,0.5)*a1, magenta+linewidth(1)); draw(shift(0.5,0.5)*((8,6)--(9,6)), magenta+linewidth(1)); [/asy][/asy]

A sickle, a staircase, and an engineer! Solved with NTguy and kotmhn . Claim: (Engineer's claim) the answer is $4\left(\lfloor n/2 \rfloor^2-1\right )$ for an $n \times n$ grid where $n \equiv 3 \pmod 4, n>3$. Proof of maximality: Label the rows from the bottom to the top as $1,2,...,n$ and the columns from left to right similarly. Label the odd-numbered rows as $1,2,1,2,1,2$... and the even rows as $3,4,3,4,...$ Observe that every $4$ can be connected by a sequence of sickles and staircases.

Observe that each sickle and staircase contains a $1$,$2$, and $3$. Hence, the number of points in a cycle must be $4\times$ number of $4$s in the grid. Color the $4$s black or white alternatively, with the first $4$ in the second row being white. There are a total of $\lfloor n/2 \rfloor ^2$. Observe that this is an odd number. Hence, the number of whites is $1$ more than the number of blacks. However, in a cycle constructed entirely out of sickles, the difference in the number of whites and the number of blacks must be an even number. In case there is a staircase, it is easy to see that there must be a $4$ which cannot belong to the cycle. Therefore, in either case we must have a $4$, which does not belong to the cycle $\implies \mathrm{maximum}\le 4\left(\lfloor n/2 \rfloor^2-1\right )$. Construction: We keep on creating an inward "spiral" as shown. It is easy to see that the desired number of squares are covered:

Beautiful Problem!, solved with MathLuis We claim that the answer is $996000$. Construction: Here, the idea is to stack "plusses" in spiral like way, while leaving some squares, here is an illustration for $11 \times 11$ grid.

Bound: Color the table by four colours as follows; A B A B A B ... C D C D C D ... A B A B A B ... C D C D C D ... Claim: The limp rook cannot cover all the cells colored $D$. Proof Firstly observe that the sequence of colors in limp rook's path must be $ABDCABDC \cdots$. We call two $D$ squares friends if they occur consecutively in the path of the limp rook, notice that any two friends must be othogonally or diagonally adjacent, Now chessboard color the squares colored with $D$, call the colors $D_1$ and $D_2$, the number of squares colored with $D_1$ is different from those colored with $D_2$, as there are odd number of squares colored $D$, therefore there exists atleast one pair of diagonally adjacent blue squares which are friends, WLOG the path of the limp rook is of the form $(a,b) \rightarrow (a,b+1) \rightarrow (a+1,b+1) \rightarrow (a+1,b+2) \rightarrow (a+2,b+2)$ where the colors of these cells are $A,B,C,D,A$ resp. Now, notice that the rook's route must also contain: $$(a-1,b+2)\rightarrow(a,b+2)\rightarrow(a,b+3)$$as we have to follow the order $ABDC \cdots$ and so we have $(a,b+3)$ connected with $(a,b)$ and $(a+2,b+2)$ with $(a-1,b+2)$ , however note that these paths intersect, contradiction! Now, to finish, the length of limp rook's path is atmost $$4\left(\left(\frac{n-1}{2}\right)^2-1\right)=996000$$