Longest path in a square grid

What is the longest path in a square grid from one corner to the diagonally opposite corner?

Edges in the grid may only be traversed once, but grid points can be used multiple times (in a square grid that means maximum twice).

After fiddling with this a while, it seems to me the following paths are the longest:

In a $2 \times 2$ grid, the longest path is $8$.

In a $3 \times 3$ grid, the longest path is $18$.

In a $4 \times 4$ grid, the longest path is $32$.

In a $5 \times 5$ grid, the longest path is $50$.

In general, the rule seems to be that the longest path for an $n \times n$ grid is $2n^2$.

Can anyone confirm this? I've searched for a proof of this, but wasn't able to find it.

Solution 1:

There are $2n(n+1)$ potential edges in the grid, but some of them need to be left out because the grid points on the boundary have only $3$ potential edges meeting, and only two of them can be in your path.

Additionally, one of the edges incident to the start and end node must be left out.

If we count the number of left-out half-edges we get at least $$ 4(n-1) + 2 = 4n-2 $$ so at least $2n-1$ of the $2n(n+1)$ edges must be missing. So at most there are $$ 2n(n+1)-(2n-1) = 2n^2 +1 $$ edges in the path.

However, the length of the path must be even: Color the grid points alternately black and white in a checkerboard pattern. Two opposite corners will have the same color, but every move changes the color, so there must be an even number of moves.

This shows that the the length of the path is at most $2n^2$.

On the other hand, it should be clear that the pattern you have found achieves this number for larger $n$ too, so it is the actual maximum.