Max packing of cars in square parking lot An $n\times n$ square grid represents a parking lot, each of the $n^2$ squares may be occupied by at most one car. However, each car (not on the boundary) must have a clear path to the boundary of the grid, moving only to adjacent squares sharing a side. 
What is the maximum number $M(n)$ of cars that can fit in the parking lot?
This was posted recently by @Benenom but for some reason was deleted 3 mins after appearing.
Clearly, $M(n)=n^2$ for $n<3$. For $n=3$ we need at least one vacant square (any non-corner square will do). For $n=4$ we need at least 3 vacant squares (eg a line of three starting from a non-corner boundary square).
At first I thought that the idea used for $n=4$ might work for all $n$. Eg for $n=8$ make vacant the first 7 squares of the third and sixth rows.
$$\begin{matrix}C&C&C&C&C&C&C&C\\
C&C&C&C&C&C&C&C\\
C&.&.&.&.&.&.&.\\
C&C&C&C&C&C&C&C\\
C&C&C&C&C&C&C&C\\
C&.&.&.&.&.&.&.\\
C&C&C&C&C&C&C&C\\
C&C&C&C&C&C&C&C\end{matrix}$$
That gives:
$M(1)=1\\
M(2)=4\\
M(3)=9-1=8\\
M(4)=16-3=13\\
M(5)=25-4=21\\
M(6)=36-2\cdot5=26\\
M(7)=49-3\cdot6=37\\
M(8)=64-2\cdot7=50$
In general we would get
$M(3n+2)=(3n+2)^2-n(3n+1)=6n^2+11n+4\\
M(3n+1)=(3n+1)^2-3n^2=6n^2+6n+1\\
M(3n)=(3n)^2-n(3n-1)=6n^2+n.$
[the last one for $n>1$]
However, as @RobPratt points out in his answer below, we can do better than that for $M(6)$, getting 36-8=28. Presumably the same is true for all $M(3n)$.
For $3n=6$ we can write the last four rows as:
$$\begin{matrix}C&.&.&.&.&.\\
C&C&.&C&.&C\\
C&C&.&C&C&C\\
C&C&C&C&C&C\end{matrix}$$
In a similar way we could write the last four rows for $3n=9$ as:
$$\begin{matrix}C&.&.&.&.&.&.&.&.\\
C&C&.&C&C&.&C&.&C\\
C&C&.&C&C&.&C&C&C\\
C&C&C&C&C&C&C&C&C\end{matrix}$$
and in general we would get $M(3n)=6n^2+2n$. The other two cases are unchanged: $M(3n+1)=6n^2+6n+1$ and $M(3n+2)=6n^2+11n+4$.
In any case I have not yet got a proof of maximality even for $M(3n+2)$.
 A: Six of your values for $M(n)$ are correct, but $M(6)=28$:
\begin{matrix}
C &C &C &C &C &C \\
C &C &. &C &C &. \\
C &C &. &C &C &C \\
C &C &. &. &. &. \\
C &C &. &C &C &C \\
C &C &C &C &C &C
\end{matrix}
And $M(7)=37$:
\begin{matrix}
C &C &. &C &C &C &C \\
C &C &. &C &. &C &C \\
C &C &. &C &. &C &C \\
C &C &. &C &. &C &C \\
C &. &. &. &. &C &C \\
C &C &C &C &C &. &C \\
C &C &C &C &C &C &C 
\end{matrix}
I used integer linear programming, with a binary variable $c_{i,j}$ to indicate whether square $(i,j)$ contains a car and a binary variable $e_{i,j}$ to indicate whether square $(i,j)$ does not contain a car but can exit the lot.  Let $N_{i,j}$ be the set of neighbors of square $(i,j)$.  The problem is to maximize $\sum_{i,j} c_{i,j}$ subject to linear constraints:
\begin{align}
c_{i,j} + e_{i,j} &\le 1 &&\text{for all $i,j$}\\
c_{i,j} &\le \sum_{(i',j')\in N_{i,j}} e_{i',j'} &&\text{for all interior $i,j$},
\end{align}
together with flow variables and constraints that send one unit of flow from each exit square to a dummy sink node.
A: Not an answer.  Just wanna report that I found another "divide-and-conquer" strategy to get the same answer for side length $m=3n$ cases.  It is based on $4$ "center aisles" forming an offset $+$ like pattern.  This divides the $m \times m$ square into $4$ rectangles, and since $m=3n$, we can arrange each rectangle to have dimensions $(3k+2) \times (3j)$, and the $(3k+2)$ side makes it in a sense easier to deal with.
Here is the $m=12=3n$ example.  The $4$ center aisles split all remaining squares into (1) four cars at the center of the $+$ denoted "b", and (2) four separate $6\times 5$ rectangles, one of which I have highlighted as "a" instead of "c".  The total number of spaces $= 5 \times 8 = 40 = n(3n-2)$, so it achieves the same $M(n)$ as the already found solution.
c c . c c . c c c c c c
c c . c c . c c c c c c
c c . c c . c . . . . .
c c . c c . c c c c c c
c c . c c . c c c c c c
c c c c c b b . . . . .
. . . . . b b a a a a a
c c c c c c . a a . a a
c c c c c c . a a . a a
. . . . . c . a a . a a
c c c c c c . a a . a a
c c c c c c . a a . a a

This also works when $m=3n$ is odd, because there is no need for the four rectangles to be the same dimensions. E.g here is the $m=9=3n$ case.  The number of spaces $=21 = n(3n-2)$, again equaling the already found solution.
c c . c c . c c c
c c . c c . c c c
c c . c c . c . .
c c . c c . c c c
c c . c c . c c c
c c c c c b b . .
. . . . . b b a a
c c c c c c . a a
c c c c c c . a a

I have played around with this "divide-and-conquer" strategy for a bit, with different original side lengths and different splits, but was never able to find a better solution.
