Number of grid points outside a rook circuit

When I draw a circuit on a 8x8 chess board that passes through all squares, no matter how many turns I draw, I always end up with 18 grid points outside my circuit (and 31 grid point inside). It looks to me that I get also constant values for any $n$ x $m$ board. Has anybody ever seen a formula of how many grid points are inside/outside for an $n$ x $n$ board? It looks obvious that there are (n/2 - 1) * (n - 2) points outside if $n$ is even, but I am searching for a proof.

If you could point me to some literature, that would be great!

Solution 1:

For an $m$ by $n$ array with $mn$ even, consider a lattice on the centres of squares. The path passes through $mn$ lattice points and contains no internal points. So, by Pick's theorem it contains an area of $\frac{mn}{2}-1$.

This area consists of unit squares centred on the 'grid points' of the question and so there are $\frac{mn}{2}-1$ enclosed grid points.

Solution 2:

The main idea here is to create a bijection from the enclosed grid points, to the area of the polygon, to the angle sum on the polygon. We will set this up in reverse.
Because the angle sum is a constant, hence the number of enclosed grid points is a constant, which we can then determine. From there, the number of exterior grid points is a constant.

Let the square be of size $ 2k \times 2k$. The question is for $k = 4$.
(It has to be of even size in order to form a circuit. The standard coloring argument applies.)

Show that

• Let the circuit connect through the mid points of the grid squares. This gives us a polygon whose (interior) corner angles are $90^\circ$ or $ 270^\circ$.
• For each grid square, there are exactly 2 lines that connect to the mid point. This splits the square into 2, one which is on the inside of the curve, and one which is on the outside of the curve. (This should be obvious, else appeal to high-power Jordan curve theorem.)
• For each mid point of a grid square, associate it to the angle that lies on the inside of the curve. This angle is either $ 90 ^ \circ, 270^\circ$ (if the mid point is also a corner of the polygon, then it's equal to the interior angle), or $180^\circ$ (if the mid point lies within an edge of the polygon).
• For each mid point of a grid square, the associated angle is also equal to "$180 ^ \circ -$ exterior angle of the polygon". Note that I'm taking "exterior angle = $180^\circ - $interior angle" as a signed angle, which could be negative. (Verify this for mid points that are on the edges and corners of the polygon.).
• There are $4k^2$ such mid points of the grid squares.
• The sum of all associated angles is thus
  $\sum_{\text{mid point}}(180 ^ \circ -$ exterior angle) = $180^\circ \times 4k^2 - \sum $ exterior angles$ = 180^\circ \times 4k^2 - 360^\circ$ . (Using that summation of signed exterior angles for a non-self intersecting polygon is $360^\circ$.)
• Show that there is a bijection between each $90^\circ$ angle and the (obvious) $\frac{1}{2} \times \frac{1}{2}$ square that is contained within the curve. (There's some work here to establish the seemingly obvious bijection.)
• Hence, the area enclosed by the curve is $ \frac{1}{4} \frac{1}{90^\circ} (180^\circ \times 4k^2 - 360^\circ) = 2k^2 - 1 $.
• Show that there is a bijection between an enclosed grid point and the $1 \times 1$ square around it (which intersects 4 grid squares) that lies within the polygon. (There's some work here to establish the seemingly obvious bijection.)
• Each enclosed grid point contributes exactly 1 to the area, hence there are $ 2k^2 -1 $ enclosed grid points.
• Since there are $(2k-1)^2$ grid points, there are $ (2k-1)^2 - (2k^2 -1) = 2(k-1)^2$ excluded grid points.

For the general $ n \times m$ grid where $nm$ is even, you can follow the above proof to conclude that

• area of enclosed polygon is $nm/2-1$, hence so is the number of enclosed grid points
• $(n-1)(m-1)$ grid points,
• $(n-1)(m-1) - ( nm/2 - 1) = \frac{1}{2} (n-2)(m-2)$ excluded grid points.