Snake algorithm that minimizes straight lines How can I find the non-self-intersecting loop that uses the least amount of straight lines (curves left/right as often as possible every turn) and still loops back on itself?
Here's an example we have calculated for 8x8:

Here is an example we have calculated for a 6x6:

 A: This problem is a special case of the quadratic traveling salesman problem in which the cost for traversing three consecutive nodes that have no turn is $1$ and the cost is $0$ otherwise.  Because your graph is bipartite, the problem is infeasible when the number of nodes is odd.  For $n\in\{2,4,6,8\}$, the optimal objective values are $0, 4, 8, 8$, so your two examples are optimal.  For $n=10$, the optimal objective value is $12$:

For $n=12$, the optimal objective value is $12$:

For $10 \times 14$, the optimal objective value is $14$:

A: For a $m\times n$ rectangle (where $mn$ must be even), denote by $f(m,n)$ the minimal number of cell centers with straight lines (centers corresponding to lattice points in the below images).
I can show at least that for a $4a\times 2b$ rectangle, we have $f(4a,2b)\le 4a$.
The following construction is somewhat canonical, given the snake like shape at a "higher level", i.e. when looking in terms of $4\times4$ subsquares. It starts with the construction in the first image for $f(12,12)=12$ (which is optimal by RobPratt's answer). Cloning a pair of middle rows in the way an Excel table would do it, $f$ does not increase, thus we obtain $f(12,12+2k)\le 12$. And the four columns in the yellow frame may be cloned by mirroring horizontally, which makes for a bigger snake and increases $f$ by $4$, thus $f(16,12+2k)\le 16$. The second image should be self-explaining how to iterate that.

I am sure that the bound is sharp whenever $2b\ge4a$. As said in the comments, looking at what are the blue components in RobPratt's pictures (i.e. the "zigzag parts" in the loop), it is quite clear that the number of those components is a lower bound for $f$, as each "corner" between them needs at least one straight segment to link them without self-overlap or unconnected corner points. But this argument would still need to be made rigorous. It would very probably imply $f(m,n)\ge\min(m,n)$, which would then be sharp whenever $\min(m,n)\equiv0\pmod4$ and $n$ even. (It seems like when one of the sides is odd, $f$ is bigger and does not only depend on the minimum.)
