First, thanks to OP for a great original puzzle. I think this is one of those problems where it's easier to think about a more general case, so imagine that our car park is mxn in size rather than 7x7. Let me speak in intuitive terms without proofs for now.
As m & n get big, the maximum number of cars we can accommodate will be about
2mn/3.
The set of access vertices will form a tree graph, and most vertices on this graph will have degree 2. Most parking vertices will have access to exactly one access vertex.
Edge effects are more noticeable for smaller m & n. Parking can be tightest if 3 divides m or n.
Suppose m,n >= 3 and F(m,n) is the maximum number of cars that can be accommodated in an mxn car park. Then:
F(m,n) = 2m-1 + F(m,n-3) = 2m+2n-8 + F(m-3,n-3). Note that removing three rows or three columns can be done in either order. So for example F(7,7) = 20 + F(4,4). The best I can do with 4x4 is 8. 20+8 = 28, which agrees with others.
So for the overall formula for F(m,n):
small cases:
F(1,1) = 0
F(1,n) = 1, if n>1
F(2,n) = n
F(3,n) = 2n-1
Now if a & b are drawn from {1,2,3} and k & l are non-negative numbers, then:
F(a+3k,b+3l) = F(a,b) + 6kl + (2a-1)l + (2b-1)k
See that if k&l are large compared to a&b, this is approx 6kl = 2mn/3
Edit: I want to correct an error. Also please can you tell me a good graphical tool to produce the lovely diagrams that you guys have been generating.
So what's going on? Let's fully solve first the case where 3 divides both length and width. Let's follow the convention that the top left corner is where the exit is. We extend an existing rectangular car park by sticking a 3 by 3z slab on the bottom or the right. The extension will contain a T-shaped corridor. This will allow access to all the corner spaces and (for free) builds the stub corridor out to the walls that we will need if we extend to the bottom or right.
What I got wrong was that I assumed that these extensions could be done in any order. In fact, every extension has a price. You therefore want to have a minimum of them. Thus instead of extending either to the right or the bottom, you should always minimize the number of extensions. Hence if I have a 3x by 3y car park, where x>=y, then I should always build it up out of y copies of 3x by 3.
A minor point is that the first 3x by 3 car park does not have a stub until we need to build out the first extension. After that, the stubs come for free.
So I claim that:
if $x>=y>1$,
then $F(3x,3y) = y*(6x-1) - 1$.
Tell me if you agree about this case, and then I will extend to other cases, and go back and change the overall proof.
