Answer to OP's question (proof follows):
For Hamitlonian paths: if $n$ is even max turns=$n^2-n$
if $n$ is odd max turns equals $n^2-n-1$
The minimum number of turns on an Hamiltonian path on an $n \times n$ lattice is $2n-2$ which can be constructed at least two non-isomorphic ways (rows or spiral) for each graph. The maximum number of turns Hamiltonian path onin a $2 \times n$ lattice is also $2n-2$
To maximize the number of turns, if $n$ is even then you can consider the graph to be a collection of $n \times 2$ graphs each of which can have a maximum of $2n-2$ turns in them starting from an outside corner on each side the $-2$ factor comes from the fact that in order to turn the corner you must have one vertex that does not turn, for an outside $2 \times n$ you lose one going into the corner and one from the starting/ending vertex. For the interior $2 \times n$'s you must have one "straight vertex coming in and one coming out.
$2n-2 \times (n/2)$seperate rectangles gives a formula of $n^2-n$ for even $n$.
If $n$ is odd, it is not so simple to construct a path because the rows do not divide evenly by $2$. The cases for constrcution of a maximal turning path are different if $n$ is 1 or 3 mod $4$.
If $n=1$ mod $4$ you begin again at a corner in the first row you again have $2n-2$ turning vertices in the first $2\times n$ rectangle. You then continue down the side of the graph (a $2\times (n-2)$ rectangle) and collect $2n-4-1$ more turning vertices. Repeat on the bottom of the graph. Continue towards the starting corner now you have a $2 \times (n-4)$ rectangle that yields $2n-8-1$ turning vertices. Continue on towards the center every two new directions you turn the rectangle get smaller and there are $4$ fewer vertices. When you reach the center (where the path ends) you gain only 1 turn for the final $3$ vertices.
Putting it all together there are $n-2$ turns in the first rectangle, $1$ turn for the center and the spiral which contains $n-7+4$ rectangles in sets of two beginning with $2n-5$ turns and adding $4$ less for every set. $2n-2+1+[(n-3)(\frac{2n+5-5}{2})]=n^2-n-1$
If $n=3$ mod $4$ then you can proceed as above but the actual center vertex of the graph is contained in the last rectangle before the end of the paththe last $3$ vertices and their $1$ turn remains the same but the path is off-centered in the graph. The formula for the vertices remains the same $2n-2$ for the first rectangle $n-5$ rectangles at an average of $n$ turns per spiral rectangle and one for the last turn of the path still sums to $n^2-n-1$ for all odd $n$.
Answer to question asked in comments.
For Hamiltonian Cycles
If $n$ is odd there is no hamiltonian cycle on a $n \times n$ grid. This can be proved from the contrapositive of theorem 3.16 on page 214 of "Graphs and Digraphs" by Chartrand. By numbering the vertices of an odd $n \times n$ grid from left to right top to bottom from $1,2,3...n^2$ Select the set of vertices $S$ as all the even numbered vertices. Then $|S|=\frac{n^2-1}{2}$ and there are $\frac{n^2+1}{2}$ disconnected components so the graph cannot be hamiltonian.
If $n$ is even you can construct a "spiral" cycle like the spirals for the odd paths given above. I haven't found a closed form expression yet that deals with the center of the cycle. $(\frac{3n^2}{4}+\frac{3n}{2}-12)+C$ where $C$ is the number of turns at the center of the graph is a good description of the maximum number of turns in a hamiltonian cycle on a $n \times n$ grid.
For context: a result of Pósa says that a random graph with $C n \log n$ edges already contains a Hamiltonian path with probability tending to $1$, and here we have a uniformly random graph (with $\frac{n^2}{4}$ edges on average). So we can be fairly wasteful.
As far as an algorithm goes, we can take the algorithm used to prove Dirac's theorem. The hypotheses of that theorem don't hold here, but the algorithm will still work with high probability. The strategy is this:
- Pick a path greedily: start at a vertex $v_1$, pick a vertex $v_2$ it is adjacent to, then pick a vertex $v_3$ adjacent to $v_2$, and so on. Repeat until you get stuck.
- Turn the path into a cycle: if it has endpoints $v_1$ and $v_\ell$, find adjacent vertices $v_i$ and $v_{i+1}$ on the path such that $v_{i+1}$ is adjacent to $v_1$ and $v_i$ is adjacent to $v_\ell$. Then the cycle is $v_1, \dots, v_i, v_\ell, \dots, v_{i+1}, v_1$.
- Turn the cycle into a longer path: if $v_{\ell+1}$ is a vertex not on the cycle, find a vertex $v$ on the cycle adjacent to $v_{\ell+1}$, and take the path starting next to $v$, going around the cycle, and then going to $v_{\ell+1}$.
- Repeat steps 2 and 3 until the path contains all the vertices.
All of these steps are quite likely to work individually. The problem is that to analyze how likely they are to work as a whole, we'd have to check edges of the graph multiple times, which doesn't preserve independence.
So instead, we will write our uniformly random graph $G$ as the union of graphs $G_0, G_1, \dots, G_{10 \log n}$, where $G_0$ contains each edge independently with probability $\frac14$, and $G_1, \dots, G_{10 \log n}$ contain each edge independently with probability $p$, chosen so that $\frac34(1-p)^{10 \log n} = \frac12$. Then the union will contain each edge with probability $\frac12$, so it will be the uniformly random graph. If we solve for $p$, we get $p = O(\frac{1}{\log n})$, but all we'll really need is for $p$ to be asymptotically bigger than $\frac{1}{\sqrt n}$.
Then I claim that:
- A greedy path chosen in $G_0$ will reach length $n - 5\log n$ with very high probability.
- Doing step 2 of the algorithm in any of the $G_1, \dots, G_{10 \log n}$ will work with very high probability.
- Doing step 3 of the algorithm in any of the $G_1, \dots, G_{10 \log n}$ will work with very high probability.
Then we can just look at graphs $G_0, G_1, \dots$ sequentially as we go through the algorithm. This preserves independence, and if the edges we need will be in the graph $G_i$ we're looking at, they will be in the union $G$.
For the first claim: the probability that a greedy path will get stuck while there's still $5 \log n$ vertices to pick from is $(\frac34)^{5\log n} = n^{-5\log \frac43}$, so the probability is at most $n^{1 - 5\log \frac43} \approx n^{-0.43}$ that it ever gets stuck.
For the second claim: we have at least $\frac n2$ options for vertices $v_i$ and $v_{i+1}$, and each one works with probability $p^2$. The probability that none of them work is $(1-p^2)^{n/2} \le e^{-p^2n/2}$, which approaches $0$ as $n\to \infty$. (This is where we want $p \gg \frac{1}{\sqrt n}$, so that the exponent goes to $-\infty$ as $n\to\infty$. We actually want a bit better than that, because we want all $O(\log n)$ of these steps to work, so the probability should go to $0$ faster than $\frac{1}{\log n}$. But our $p$ is actually quite a bit larger than $\frac{1}{\sqrt n}$, so we have that wiggle room.)
For the third claim: we have at least $\frac n2$ options for the vertex $v$, and each works with probability $p$. The probability that none of them work is $(1-p)^{n/2} \le e^{-pn/2}$, which approaches $0$ as $n\to \infty$.
Best Answer
Hint in the Form of Leading Questions. What color is the upper left corner square? What color is the lower right corner square? What happens to the color of the pawn's square on each step? How many steps must the pawn take?