It's possible to have length at least $rn^2$ for any $0 < r < 1$. Choose a large positive integer $m$ and a large even positive integer $h$. Let $w = mh + m - 1$. We'll make a board formed from $m$ vertically stacked rectangular blocks of size $w \times h$ with collapsing margins of size one square around each block. This creates a $(w + 2) \times (w + 2)$ board. Define an F-block to be a zigzag by row through a rectangular $w \times h$ block from bottom left to top left, as shown below. We'll use green rectangles to mark these. [asy][asy] size(4cm); //for (int y = 0; y <= 15; y += 1) { // draw((-1.5, y-0.5)--(12.5, y-0.5), gray(0.8)); //} //for (int x = 0; x <= 12; x += 1) { // draw((x-0.5, -1.5)--(x-0.5, 15.5), gray(0.8)); //} //draw((-1.5,-1.5)--(12.5,-1.5)--(12.5,15.5)--(-1.5,15.5)--cycle, gray(0.5)); draw((0,0)--(10,0)--(10,1)--(0,1)--(0,2)--(10,2)--(10,3)--(0,3)--(0,4)--(10,4)--(10,5)--(0,5), EndArrow); dot((0,0)); path p = (-0.5, 7.5)--(10.5, 7.5)--(10.5, 13.5)--(-0.5, 13.5)--cycle; fill(p, green); draw(p); label("$F$", (5, 10.5)); dot((0,8)); dot((0,13)); [/asy][/asy] Define an R-block to be an F-block reversed. We'll use orange rectangles to mark these. [asy][asy] size(4cm); //for (int y = 0; y <= 15; y += 1) { // draw((-1.5, y-0.5)--(12.5, y-0.5), gray(0.8)); //} //for (int x = 0; x <= 12; x += 1) { // draw((x-0.5, -1.5)--(x-0.5, 15.5), gray(0.8)); //} //draw((-1.5,-1.5)--(12.5,-1.5)--(12.5,15.5)--(-1.5,15.5)--cycle, gray(0.5)); draw((0,0)--(10,0)--(10,1)--(0,1)--(0,2)--(10,2)--(10,3)--(0,3)--(0,4)--(10,4)--(10,5)--(0,5), BeginArrow); dot((0,5)); path p = (-0.5, 7.5)--(10.5, 7.5)--(10.5, 13.5)--(-0.5, 13.5)--cycle; fill(p, orange); draw(p); label("$R$", (5, 10.5)); dot((0,8)); dot((0,13)); [/asy][/asy] Now for the snake in our grid. Initially, the top block is empty, and we have F blocks in the remaining $m-1$ blocks going from bottom to top. As $h$ goes to infinity, the size of this snake approaches $\frac{m-1}{m}$ of the area of the board, which can be made as close to 1 as we want by increasing $m$. Now we'll show we can reverse it. Here's an example for $m = 4$ and $h = 6$. [asy][asy] size(6cm); for (int y = 0; y <= 27; y += 1) { draw((-1.5, y-0.5)--(27.5, y-0.5), gray(0.8)); } for (int x = 0; x <= 27; x += 1) { draw((x-0.5, -1.5)--(x-0.5, 27.5), gray(0.8)); } draw((-1.5,-1.5)--(27.5,-1.5)--(27.5,27.5)--(-1.5,27.5)--cycle, gray(0.5)); path p0 = (-0.5, -0.5)--(26.5, -0.5)--(26.5, 5.5)--(-0.5, 5.5)--cycle; void drawF(real dx, real dy) { path p = shift((dx,dy))*p0; fill(p, green); draw(p); label("$F$", (13+dx, 2.5+dy)); dot((dx,dy)); dot((dx,5+dy)); } drawF(0, 0); drawF(0, 7); drawF(0, 14); draw((0,5)--(0,7)); draw((0,12)--(0,14)); [/asy][/asy] First, we have the snake wrap around the right column to form an R-block at the top, which vacates the bottom. The snake will then move along the left column back to where its tail was. [asy][asy] size(6cm); for (int y = 0; y <= 27; y += 1) { draw((-1.5, y-0.5)--(27.5, y-0.5), gray(0.8)); } for (int x = 0; x <= 27; x += 1) { draw((x-0.5, -1.5)--(x-0.5, 27.5), gray(0.8)); } draw((-1.5,-1.5)--(27.5,-1.5)--(27.5,27.5)--(-1.5,27.5)--cycle, gray(0.5)); path p0 = (-0.5, -0.5)--(26.5, -0.5)--(26.5, 5.5)--(-0.5, 5.5)--cycle; void drawF(real dx, real dy) { path p = shift((dx,dy))*p0; fill(p, green); draw(p); label("$F$", (13+dx, 2.5+dy)); dot((dx,dy)); dot((dx,5+dy)); } void drawR(real dx, real dy) { path p = shift((dx,dy))*p0; fill(p, orange); draw(p); label("$R$", (13+dx, 2.5+dy)); dot((dx,dy)); dot((dx,5+dy)); } //drawF(0, 0); drawF(0, 7); drawF(0, 14); drawR(0, 21); draw((0,12)--(0,14)); draw((0,19)--(0,20)--(27,20)--(27,27)--(0,27)--(0,26)); draw((0,21)--(-1,21)--(-1,0)--(0,0)); [/asy][/asy] We then recreate the snake we had before, except where the top F-block was, we'll keep the R-block in the top position. We still use the right column to wrap around. This means the secondmost top block is vacant; the snake will avoid entering it. [asy][asy] size(6cm); for (int y = 0; y <= 27; y += 1) { draw((-1.5, y-0.5)--(27.5, y-0.5), gray(0.8)); } for (int x = 0; x <= 27; x += 1) { draw((x-0.5, -1.5)--(x-0.5, 27.5), gray(0.8)); } draw((-1.5,-1.5)--(27.5,-1.5)--(27.5,27.5)--(-1.5,27.5)--cycle, gray(0.5)); path p0 = (-0.5, -0.5)--(26.5, -0.5)--(26.5, 5.5)--(-0.5, 5.5)--cycle; void drawF(real dx, real dy) { path p = shift((dx,dy))*p0; fill(p, green); draw(p); label("$F$", (13+dx, 2.5+dy)); dot((dx,dy)); dot((dx,5+dy)); } void drawR(real dx, real dy) { path p = shift((dx,dy))*p0; fill(p, orange); draw(p); label("$R$", (13+dx, 2.5+dy)); dot((dx,dy)); dot((dx,5+dy)); } drawF(0, 0); drawF(0, 7); //drawF(0, 14); drawR(0, 21); draw((0,5)--(0,7)); draw((0,12)--(0,13)--(27,13)--(27,27)--(0,27)--(0,26)); [/asy][/asy] From here, we make a second R-block below the first one, then go along the left column back to the original tail. [asy][asy] size(6cm); for (int y = 0; y <= 27; y += 1) { draw((-1.5, y-0.5)--(27.5, y-0.5), gray(0.8)); } for (int x = 0; x <= 27; x += 1) { draw((x-0.5, -1.5)--(x-0.5, 27.5), gray(0.8)); } draw((-1.5,-1.5)--(27.5,-1.5)--(27.5,27.5)--(-1.5,27.5)--cycle, gray(0.5)); path p0 = (-0.5, -0.5)--(26.5, -0.5)--(26.5, 5.5)--(-0.5, 5.5)--cycle; void drawF(real dx, real dy) { path p = shift((dx,dy))*p0; fill(p, green); draw(p); label("$F$", (13+dx, 2.5+dy)); dot((dx,dy)); dot((dx,5+dy)); } void drawR(real dx, real dy) { path p = shift((dx,dy))*p0; fill(p, orange); draw(p); label("$R$", (13+dx, 2.5+dy)); dot((dx,dy)); dot((dx,5+dy)); } //drawF(0, 0); drawF(0, 7); drawR(0, 14); drawR(0, 21); draw((0,12)--(0,13)--(27,13)--(27,27)--(0,27)--(0,26)); draw((0,21)--(0,19)); draw((0,14)--(-1,14)--(-1,0)--(0,0)); [/asy][/asy] Now we'll recreate the snake we started with, but with two less F-blocks and two R-blocks at the top. The thirdmost top block is vacant. [asy][asy] size(6cm); for (int y = 0; y <= 27; y += 1) { draw((-1.5, y-0.5)--(27.5, y-0.5), gray(0.8)); } for (int x = 0; x <= 27; x += 1) { draw((x-0.5, -1.5)--(x-0.5, 27.5), gray(0.8)); } draw((-1.5,-1.5)--(27.5,-1.5)--(27.5,27.5)--(-1.5,27.5)--cycle, gray(0.5)); path p0 = (-0.5, -0.5)--(26.5, -0.5)--(26.5, 5.5)--(-0.5, 5.5)--cycle; void drawF(real dx, real dy) { path p = shift((dx,dy))*p0; fill(p, green); draw(p); label("$F$", (13+dx, 2.5+dy)); dot((dx,dy)); dot((dx,5+dy)); } void drawR(real dx, real dy) { path p = shift((dx,dy))*p0; fill(p, orange); draw(p); label("$R$", (13+dx, 2.5+dy)); dot((dx,dy)); dot((dx,5+dy)); } drawF(0, 0); //drawF(0, 7); drawR(0, 14); drawR(0, 21); draw((0,5)--(0,6)--(27,6)--(27,27)--(0,27)--(0,26)); draw((0,21)--(0,19)); [/asy][/asy] So far we have described two repetitions of a procedure we want to repeat $m-2$ times total. After that, we have one F-block and $m-2$ R-blocks, with the secondmost bottom block vacant. (For $m = 4$ no more repetitions are needed.) Now we'll create an $(m-1)$st R-block below the $m-2$ we have already, leaving the bottom block vacant. [asy][asy] size(6cm); for (int y = 0; y <= 27; y += 1) { draw((-1.5, y-0.5)--(27.5, y-0.5), gray(0.8)); } for (int x = 0; x <= 27; x += 1) { draw((x-0.5, -1.5)--(x-0.5, 27.5), gray(0.8)); } draw((-1.5,-1.5)--(27.5,-1.5)--(27.5,27.5)--(-1.5,27.5)--cycle, gray(0.5)); path p0 = (-0.5, -0.5)--(26.5, -0.5)--(26.5, 5.5)--(-0.5, 5.5)--cycle; void drawF(real dx, real dy) { path p = shift((dx,dy))*p0; fill(p, green); draw(p); label("$F$", (13+dx, 2.5+dy)); dot((dx,dy)); dot((dx,5+dy)); } void drawR(real dx, real dy) { path p = shift((dx,dy))*p0; fill(p, orange); draw(p); label("$R$", (13+dx, 2.5+dy)); dot((dx,dy)); dot((dx,5+dy)); } //drawF(0, 0); drawR(0, 7); drawR(0, 14); drawR(0, 21); draw((0,21)--(0,19)); draw((0,14)--(0,12)); [/asy][/asy] The snake can now easily form an R-block in the bottom position without wrapping, which vacates the top. [asy][asy] size(6cm); for (int y = 0; y <= 27; y += 1) { draw((-1.5, y-0.5)--(27.5, y-0.5), gray(0.8)); } for (int x = 0; x <= 27; x += 1) { draw((x-0.5, -1.5)--(x-0.5, 27.5), gray(0.8)); } draw((-1.5,-1.5)--(27.5,-1.5)--(27.5,27.5)--(-1.5,27.5)--cycle, gray(0.5)); path p0 = (-0.5, -0.5)--(26.5, -0.5)--(26.5, 5.5)--(-0.5, 5.5)--cycle; void drawF(real dx, real dy) { path p = shift((dx,dy))*p0; fill(p, green); draw(p); label("$F$", (13+dx, 2.5+dy)); dot((dx,dy)); dot((dx,5+dy)); } void drawR(real dx, real dy) { path p = shift((dx,dy))*p0; fill(p, orange); draw(p); label("$R$", (13+dx, 2.5+dy)); dot((dx,dy)); dot((dx,5+dy)); } drawR(0, 0); drawR(0, 7); drawR(0, 14); //drawR(0, 21); draw((0,14)--(0,12)); draw((0,7)--(0,5)); [/asy][/asy] And we're done.

Refer to unit squares by the coordinates with down-left corner $(0,0)$. Define the head of the snake to be $s_1$, tail to be any sequence $(s_k,s_{k-1},...,s_j)$. We provide a strategy for any constant $\varepsilon \in (0.1)$. Let $S_i=(n-2i+1,n-1), A_i=(n-2i+1,3), B_i = (n-2i, 3),C_i = (n-2i, n-1)$. Construct initial snake $S_1A_1B_1C_1S_2A_2B_2C_2...S_{k-1}A_{k-1}B_{k-1}C_{k-1}S_kA_k$ so that $n-2k+1 \ge 8$. First change the snake to $C_3S_4A_4B_4C_4...S_{k+2}A_{k+2}B_{k+2}C_{k+2}S_{k+3}$, then move its head down until its $y$ coordinate becomes $2$, and let it turn right and move all the way to the square right below $A_2$, then turn 90 degrees and move to $A_2$, then moving up vertically until hitting $S_2$, then move to $C_1$ and down to $B_1$, then to $A_1, S_1, M:=(n,n-1),$ and up to $N:=(n,n)$, then to the square $T_3$ right above $S_3$, then go to $S_3$ and then visit the squares $A_3,B_3,C_3,...,S_k,A_k,B_k,C_k$. Now the snake is $A_2S_2C_1B_1A_1S_1(MNT_3)S_3A_3B_3C_3...S_kA_kB_kC_k$ with a portion of tail truncated. Now repeat the above procedure starting from snake $A_{i+1}S_{i+1}C_iB_iA_iS_i...C_1B_1A_1S_1(MNT_{i+2})-S_{i+2}A_{i+2}B_{i+2}C_{i+2}...S_kA_kB_kC_k - tail$, to increase $i$ by $1$. Eventually $i=k$. By the choice $n-2k+1 \ge 8$ the snake never hits itself when $n$ is large enough, so we are done.

The answer is yes (and $0.9$ is arbitrary). The following solution is due to Brian Lawrence. For illustration reasons, we give below a figure of a snake of length $89$ turning around in an $11 \times 11$ square (which generalizes readily to odd $n$). We will see that a snake of length $(n-1)(n-2)-1$ can turn around in an $n \times n$ square, so this certainly implies the problem. [asy][asy]unitsize(0.25cm); defaultpen(fontsize(8pt)); int n = 0; picture snake(path p) { picture pic; draw(pic, shift(-0.5,-0.5)*scale(11)*unitsquare, black+1); for (int i=0; i<=10; ++i) { for (int j=0; j<=10; ++j) { if ( (i+j) % 2 == 0 ) fill(pic, shift(i-0.5,j-0.5)*unitsquare, rgb(0.7, 0.7, 0.7)); } } path q = subpath(p, arctime(p, arclength(p)-88), arctime(p, arclength(p))); draw(pic, q, deepgreen+1.3, EndArrow(TeXHead,1.3)); ++n; label(pic, "Figure " + (string) n, (5,0), 2*dir(-90)); return pic; } real M = 13; add(snake( (0,1)--(0,10)-- (8,10)--(8,9)--(1,9)--(1,8)--(8,8)--(8,7)--(1,7)--(1,6)-- (8,6)-- (8,5)--(1,5)--(1,4)--(8,4)--(8,3)--(1,3)--(1,2)-- (8,2)--(8,1)--(1,1))); add(shift(M,0)*snake((7,9)-- (1,9)--(1,8)--(8,8)--(8,7)--(1,7)--(1,6)--(8,6)--(8,5)-- (1,5)--(1,4)--(8,4)--(8,3)--(1,3)--(1,2)--(8,2)--(8,1)-- (1,1)--(1,0)--(10,0)--(10,9))); add(shift(2*M,0)*snake(shift(-1,1)*((7,9)-- (1,9)--(1,8)--(8,8)--(8,7)--(1,7)--(1,6)--(8,6)--(8,5)-- (1,5)--(1,4)--(8,4)--(8,3)--(1,3)--(1,2)--(8,2)--(8,1)-- (1,1)--(1,0)--(10,0)--(10,9)))); add(shift(3*M,0)*snake( (0,9)--(7,9)--(7,8)--(0,8)--(0,7)--(7,7)--(7,6)-- (0,6)--(0,5)--(7,5)--(7,4)--(0,4)--(0,3)--(7,3)--(7,2)-- (0,2)--(0,1)--(9,1)--(9,10)--(2,10))); add(shift(0,-M)*snake( (0,9)--(7,9)--(7,8)--(0,8)--(0,7)--(7,7)--(7,6)-- (0,6)--(0,5)--(7,5)--(7,4)--(0,4)--(0,3)--(7,3)--(7,2)-- (0,2)--(0,1)--(9,1)-- (9,2)--(8,2)--(8,3)--(9,3)-- (9,10)--(4,10))); add(shift(M,-M)*snake( (0,9)--(7,9)--(7,8)--(0,8)--(0,7)--(7,7)--(7,6)-- (0,6)--(0,5)--(7,5)--(7,4)--(0,4)--(0,3)--(6,3)--(6,2)-- (0,2)--(0,1)--(9,1)-- (9,2)--(8,2)--(8,3)--(9,3)-- (9,10)--(2,10))); add(shift(2*M,-M)*snake( (0,9)--(5,9)--(5,8)--(0,8)--(0,7)--(3,7)--(3,6)-- (0,6)--(0,5)--(1,5)--(1,4)--(0,4)--(0,3)--(0,3)--(0,2)-- (0,2)--(0,1)--(9,1)--(9,2)-- (2,2)--(2,3)--(9,3)--(9,4)--(3,4)--(3,5)--(9,5)--(9,6)-- (5,6)--(5,7)--(9,7)--(9,8)--(7,8)--(7,9)--(9,9)--(9,10)--(2,10) )); add(shift(3*M,-M)*snake((0,9)-- (0,2)--(0,1)--(9,1)--(9,2)-- (2,2)--(2,3)--(9,3)--(9,4)--(2,4)--(2,5)--(9,5)--(9,6)-- (2,6)--(2,7)--(9,7)--(9,8)--(2,8)--(2,9)--(9,9)--(9,10)--(2,10) )); add(shift(0,-2*M)*snake((0,7)-- (0,2)--(0,1)--(9,1)--(9,2)-- (1,2)--(1,3)--(9,3)--(9,4)--(2,4)--(2,5)--(9,5)--(9,6)-- (2,6)--(2,7)--(9,7)--(9,8)--(2,8)--(2,9)--(9,9)--(9,10)--(2,10) )); add(shift(M,-2*M)*snake( (0,1)--(9,1)--(9,2)-- (1,2)--(1,3)--(9,3)--(9,4)--(1,4)--(1,5)--(9,5)--(9,6)-- (1,6)--(1,7)--(9,7)--(9,8)--(1,8)--(1,9)--(9,9)--(9,10)--(2,10) )); add(shift(2*M,-2*M)*snake((0,1)--(8,1)--(8,2)-- (1,2)--(1,3)--(8,3)--(8,4)--(1,4)--(1,5)--(9,5)--(9,6)-- (1,6)--(1,7)--(9,7)--(9,8)--(1,8)--(1,9)--(9,9)--(9,10)-- (0,10)--(0,8) )); add(shift(3*M,-2*M)*snake((0,1)--(8,1)--(8,2)-- (1,2)--(1,3)--(8,3)--(8,4)--(1,4)--(1,5)--(8,5)--(8,6)-- (1,6)--(1,7)--(8,7)--(8,8)--(1,8)--(1,9)--(8,9)--(8,10)-- (0,10)--(0,2) )); [/asy][/asy] Use the obvious coordinate system with $(1,1)$ in the bottom left. Start with the snake as shown in Figure 1, then have it move to $(2,1)$, $(2,n)$, $(n,n-1)$ as in Figure 2. Then, have the snake shift to the position in Figure 3; this is possible since the snake can just walk to $(n,n)$, then start walking to the left and then follow the route; by the time it reaches the $i$th row from the top its tail will have vacated by then. Once it achieves Figure 3, move the head of the snake to $(3,n)$ to achieve Figure 4. In Figure 5 and 6, the snake begins to ``deform'' its loop continuously. In general, this deformation by two squares is possible in the following way. The snake walks first to $(1,n)$ then retraces the steps left by its tail, except when it reaches $(n-1,3)$ it makes a brief detour to $(n-2,3)$, $(n-2,4)$, $(n-1,4)$ and continues along its way; this gives the position in Figure 5. Then it retraces the entire loop again, except that when it reaches $(n-4,4)$ it turns directly down, and continues retracing its path; thus at the end of this second revolution, we arrive at Figure 6. By repeatedly doing perturbations of two cells, we can move move all the ``bumps'' in the path gradually to protrude from the right; Figure 7 shows a partial application of the procedure, with the final state as shown in Figure 8. In Figure 9, we stretch the bottom-most bump by two more cells; this shortens the ``tail'' by two units, which is fine. Doing this for all $(n-3)/2$ bumps arrives at the situation in Figure 10, with the snake's head at $(3,n)$. We then begin deforming the turns on the bottom-right by two steps each as in Figure 11, which visually will increase the length of the head. Doing this arrives finally at the situation in Figure 12. Thus the snake has turned around.

The answer is yes. We will show that there is a snake of length $(2k + 1)(2k + 3)$ which can turn around in a $2k + 5$ by $2k + 5$ grid, which will imply the answer because $\frac{(2k + 1)(2k + 3)}{(2k + 5)^2} > 0.9$ for sufficiently large $k.$ Number the rows $1$ to $2k + 5$ from top to bottom, and columns $1$ to $2k + 5$ from left to right. Have the snake occupy the leftmost $2k + 1$ columns and the middle $2k + 3$ rows, starting from the top-left and alternating between going down and up columns. Diagram[asy][asy] DefaultHead.size=new real(pen p=currentpen) {return 2.5mm;}; unitsize(0.4cm); void drawGrid(int r, int c) { for (int i = 0; i <= r; ++i) { draw((0, i)--(c, i)); } for (int i = 0; i <= c; ++i) { draw((i, 0)--(i, r)); } } drawGrid(13, 13); void drawSnake(pair[] joints) { for (int i = 0; i < joints.length - 2; ++i) { draw((joints[i] + (0.5, 0.5))--(joints[i + 1] + (0.5, 0.5)), deepgreen+linewidth(1.5)); } int i = joints.length - 2; draw((joints[i] + (0.5, 0.5))--(joints[i + 1] + (0.5, 0.5)), deepgreen+linewidth(1.5), EndArrow); } pair[] joints = {(0, 11), (0, 1), (1, 1), (1, 11), (2, 11), (2, 1), (3, 1), (3, 11), (4, 11), (4, 1), (5, 1), (5, 11), (6, 11), (6, 1), (7, 1), (7, 11), (8, 11), (8, 1)}; drawSnake(joints); [/asy][/asy] The main idea is to have the snake go around and reenter the left side in the opposite direction, moving the entry point right each time to gradually increase the amount of it that has turned around. For the first step, we have the snake's head move up column $2k + 2,$ down column $2k + 3,$ up column $2k + 4,$ and down column $2k + 5$ (using rows $2$ through $2k + 4$). Then have the head go down to the last row, left to the first column, and up the first column (to row $2$). The tail of the snake is in or to the right of column $6,$ because the middle $2k + 3$ rows of columns $1, 2k + 5, 2k + 4, \ldots, 6$ make up the length of the snake. Diagram[asy][asy] DefaultHead.size=new real(pen p=currentpen) {return 2.5mm;}; unitsize(0.4cm); void drawGrid(int r, int c) { for (int i = 0; i <= r; ++i) { draw((0, i)--(c, i)); } for (int i = 0; i <= c; ++i) { draw((i, 0)--(i, r)); } } drawGrid(13, 13); void drawSnake(pair[] joints) { for (int i = 0; i < joints.length - 2; ++i) { draw((joints[i] + (0.5, 0.5))--(joints[i + 1] + (0.5, 0.5)), deepgreen+linewidth(1.5)); } int i = joints.length - 2; draw((joints[i] + (0.5, 0.5))--(joints[i + 1] + (0.5, 0.5)), deepgreen+linewidth(1.5), EndArrow); } pair[] joints = {(5, 1), (5, 11), (6, 11), (6, 1), (7, 1), (7, 11), (8, 11), (8, 1), (9, 1), (9, 11), (10, 11), (10, 1), (11, 1), (11, 11), (12, 11), (12, 0), (0, 0), (0, 11)}; drawSnake(joints); [/asy][/asy] Now we enter column $5$ from the top (by first going to $(1, 1),$ then going to $(5, 1)$ through the first row, and then going down column $5$), and continue alternating between going up and down columns (using the middle $2k + 3$ rows), all the way to column $2k + 5,$ in which the snake moves down. (At this point, the tail of the snake is in or to the right of column $5.$) Then we go down to the last row, and go left to column $3.$ We enter column $3$ from the bottom and go up column $3,$ down column $2,$ and up column $1,$ using the middle $2k + 3$ rows. At this point the tail is in or to the left of column $8.$ Diagram[asy][asy] DefaultHead.size=new real(pen p=currentpen) {return 2.5mm;}; unitsize(0.4cm); void drawGrid(int r, int c) { for (int i = 0; i <= r; ++i) { draw((0, i)--(c, i)); } for (int i = 0; i <= c; ++i) { draw((i, 0)--(i, r)); } } drawGrid(13, 13); void drawSnake(pair[] joints) { for (int i = 0; i < joints.length - 2; ++i) { draw((joints[i] + (0.5, 0.5))--(joints[i + 1] + (0.5, 0.5)), deepgreen+linewidth(1.5)); } int i = joints.length - 2; draw((joints[i] + (0.5, 0.5))--(joints[i + 1] + (0.5, 0.5)), deepgreen+linewidth(1.5), EndArrow); } pair[] joints = {(7, 1), (7, 11), (8, 11), (8, 1), (9, 1), (9, 11), (10, 11), (10, 1), (11, 1), (11, 11), (12, 11), (12, 0), (2, 0), (2, 11), (1, 11), (1, 1), (0, 1), (0, 11)}; drawSnake(joints); [/asy][/asy] Now we keep repeating this step, moving to the right each time. From a position looking like this where the snake has entered row $2m + 1$ from the bottom and then gone up and down to column $1$ (so the snake's tail is in or to the left of column $2m + 6$), we move up to the first row, go right to column $2m + 5,$ enter it from the top and start going down odd columns and up even columns (in the middle $2k + 3$ rows) until we go down the last column. Then we go down to the last row, enter column $2m + 3$ from the bottom (columns $2m + 4$ to $2m + 1$ must be empty, except for possibly row $1$), and go up it, down row $2m + 2,$ and so on until we go up row $1$ (using the middle $2k + 3$ rows, again). This results in a similar position as we had started at, with $m$ replaced by $m + 1.$ Then we repeat this process again. Diagram[asy][asy] DefaultHead.size=new real(pen p=currentpen) {return 2.5mm;}; unitsize(0.4cm); void drawGrid(int r, int c) { for (int i = 0; i <= r; ++i) { draw((0, i)--(c, i)); } for (int i = 0; i <= c; ++i) { draw((i, 0)--(i, r)); } } drawGrid(13, 13); void drawSnake(pair[] joints) { for (int i = 0; i < joints.length - 2; ++i) { draw((joints[i] + (0.5, 0.5))--(joints[i + 1] + (0.5, 0.5)), deepgreen+linewidth(1.5)); } int i = joints.length - 2; draw((joints[i] + (0.5, 0.5))--(joints[i + 1] + (0.5, 0.5)), deepgreen+linewidth(1.5), EndArrow); } pair[] joints = {(9, 1), (9, 11), (10, 11), (10, 1), (11, 1), (11, 11), (12, 11), (12, 0), (4, 0), (4, 11), (3, 11), (3, 1), (2, 1), (2, 11), (1, 11), (1, 1), (0, 1), (0, 11)}; drawSnake(joints); [/asy][/asy] When we get to $m = k - 1,$ this process causes us to enter column $2k + 1$ from the bottom, and then go up it, down $2k,$ and so on (using the middle $2k + 3$ rows). When we have completed it, this means the snake has turned around.

This construction is quite similar to post 2. https://danie1.ggim.me/USATST-2019-3/main.html