# Maximum path crossings in a square grid

Make a path from one corner of a square grid to the diagonally opposite corner, using horizontal and vertical edges between the grid points. What is the maximum number of times the path can cross itself?

A path "crosses itself" when it has passed through a grid point in a straight line and later passes through the grid point again in a straight line, which is perpendicular to the first line. See example below.

Edges can only be traversed once.

For $N \times N$ grids where $N$ is odd, the problem is easy as shown for $N=5$ below:

The number of crossings here is $C= 16 = (N-1)^2$. This is also the maximum number of crossings because crossings are only possible at interior grid points, i.e. grid points which are not on the perimeter, and all interior grid points here have a crossing. This is obviously true for any grid where $N$ is odd.

But when $N$ is even, I cannot immediately find the answer. If the path were allowed to end at the same corner it started at, the solution would be easy:

The solution would again be $C=(N-1)^2$. But the path must end at the diagonally opposite corner. My best attempt for $N=4$ is shown below:

This has $C=6$ crossings. Is this the maximum possible? What is the maximum possible for even $N$?

• One may ask the same question for $N\times M$ grids, in which case you have a problem if either $M$ or $N$ is odd. You may be able to try out smaller cases however. – Bob Krueger Jul 11 '18 at 23:47