# A Special Parking Lot

There is a special kind of parking lot that stores special 1x1 cars that only can move to adjacent squares not including diagonals if they are empty (provided no car occupies the square). Every car occupies exactly one square and no more. The exit is beside the top left corner of the parking lot.

Because everyone is a perfect driver, everyone parks in a way that every car can exit without moving any other cars.

Currently, there are 24 cars parked in a 7 by 7 parking lot of this kind. Can you fit more cars in a different arrangement?

• Hi everyone, If someone doesn't find a solution more than the current maximum (see the solution from Alpha) in one week from now, I will mark it as the correct one! Basically, find a way to fit in (spoiler)(145/5)! – user35295 Oct 12 '17 at 15:26
• Allan, is this problem from the University of Calgary's "Math Nite", as Faraz says it is in comments to another question? If so, you need to say so in the question. – Gareth McCaughan Oct 21 '17 at 15:05
• SURE I TOOK IT BUT I DID POST IT BECAUSE NO ONE COULD FIND A SOLUTION. – user35295 Oct 22 '17 at 3:05
• I will Award my bounty to a random account that I will delete. Good bye in 3 Hours. – user35295 Oct 23 '17 at 0:12
• This is actually a good question. There seem to be so many solutions with 28 parking spaces but none found with 29 spaces. If there is no 29 then is there a clear way to see that 29 is impossible? – Laska Oct 24 '17 at 16:25

No idea if this is optimal (also have no proof), but it's possible to do

28

Example:

• Hi Alpha, I have attempted this puzzle already and I have found various solutions that all have 28 one of which is yours but I have not found a solution for 29. I do believe this is optimal but I also have no way to prove it so this is why I posted it on the website! – user35295 Oct 12 '17 at 15:19

In addition to explicit solutions existing for parking 28 cars (of which there are very many), some very simple rules that drivers can use when parking, always seem results in achieving this number, so a very large family of possible solutions can be generated by having 28 cars obey the following rules:

1. If you can park next to a wall without blocking anyone in, do so.
2. If all the spaces next to a wall are either taken or would block someone in, park in any available space that doesn't block anyone in.

[From this point onwards, I started answering a different question to what was originally intended, but it was a valid interpretation of the question as it stood at the time, and led to some interesting results, so I'll let it stand]

However, I don't think that's what the puzzle is asking - we're told there are already 24 cars in the car park, and asked if another one can be added... but we're not told we can move the cars already in the car park.

Even the most obvious arrangement of 24 cars in 4 columns of 6 allows for another one to be easily added:

 ################# . . . . . . . # <- add one at the top of the right "column" of cars # x . x . x . x # # x . x . x . x # # x . x . x . x # # x . x . x . x # # x . x . x . x # # x . x . x . x # #################

... and it seems trivially easy to generate layouts with 28 cars if you can move all the cars at will...

So instead another interpretation of the question seems to me to be "if you know there are 24 cars in a car park of this type can you be sure that more can be added" - i.e. either:

• demonstrate that for all possible arrangements of 24 cars according to the rules, a 25th can always be added (i.e. "yes" to the original puzzle), or
• show an arrangement of 24 cars where a 25th cannot possibly be added (i.e. "not necessarily" as an answer to the original puzzle).

I am also assuming an additional rule, not explicitly stated in the question, that drivers must not block off empty spaces - both other solutions would currently violate that rule but are easily modified to avoid it by moving 1 car adjacent to the blocked off space into it.

With this interpretation, the answer appears to be

"not necessarily"

because

No additional car can be added to the following arrangements without boxing someone in:
First layout I found: [which was wrong!] ################# . . . . x x x # # x . x . . . . # # x . x . x . x # # x . x . x . x # # x . x x x . x # # . . . x . . . # # x x . x . x x # ################# more elegant layout: ################# . . . . . . . # # . x x . x x . # # . x x . x x . # # . x x . x x . # # . x x . x x . # # . x x . x x . # # . x x . x x . # #################

This would then seem to invite the further question:

Based on the same rules, if there are 23 cars in the car park with no blocked off cars or empty space, can you always add a 24th?

or indeed

What is the smallest number of cars that can be parked in such a car park, with no blocked off cars or empty space, but so that no further cars can be added without blocking off at least one car?

As a start towards this final question,

This layout has only 21 cars parked, but I cannot see a way to add another:  ################# . . . . . . . # # . x x . x x . # # . x x . x . . # # . x . . x . x # # . x . x x . . # # . x . . x x . # # . x x . x x . # #################

After a bit more experimentation I found

a layout where only 19 cars prevent any more from being able to park without boxing someone in:  ################# . . . . . . . # # x x x x x x . # # . . . . . x . # # . x x x . x . # # . x x . . x . # # . x x x x x . # # . . . . . . . # #################

• You can add another car to the bottom row in your first layout. – Kruga Oct 12 '17 at 11:36
• If you would be allowed to move exit 1 cell down, then 29th would fit in :) – Cockabondy Oct 12 '17 at 13:28
• Hi Steve, sorry for not making the question clear, you may remove all the cars and put them back in which makes the top part of the solution kind of invalid. – user35295 Oct 12 '17 at 15:24
• The backpuzzle here – of seeking the least efficient solution – could well be posted as its own puzzle, @Steve, perhaps with different dimensions because you've already given away the 7x7 solution. This suggests a game as well, where each player tries to be the last to park, or to leave a forced spot for the other player. That, too, could be posted as a strategy puzzle, for instance by asking what parking lot dimensions favor which players. – humn Oct 13 '17 at 12:35

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.

• @Allan Cao: I explicitly took as an example F(7,7)=20+F(4,4) which is 8 as I mentioned. It goes without saying that 20+8=28. – Laska Oct 13 '17 at 3:47
• This is an excellent overview of the general case. Why would anyone vote it down? (Someone did and negated my ^vote.) – humn Oct 13 '17 at 3:51
• Hi Laska, and welcome to Puzzling. In Stack Exchange, answers should both answer the question (say 'max 28' somewhere, in this case) and show why that answer should be believed. You have a very interesting answer, but aside from your assertion that it's true, I'm not sure how you derived the starting recurrence relation or the 2mn/3 approximation. For example, does this rely on a particular packing, or is it general? I might have missed something obvious and would like to understand your derivation. – Lawrence Oct 13 '17 at 5:13
• The 4 x 4 case shown in humn's diagram can be constructed by one more layer of the same iteration, starting from a 1 x 1 grid (which can contain a car if it's not in the top-left corner, but in that case another car must be removed from the 3 x k region that is in the top-left corner) – Steve Oct 13 '17 at 11:35
• The equations are a good approximation, and I think are correct for all board sizes <=7. But I did find a counter-example. Let me make sure I'm using your equations correctly. F(3,3)=5 F(6,6)=5+16=21 F(9,9)=21+28=49 But here's a counter-example where F(9,9)=50 Parking Lot – Geoffrey Oct 18 '17 at 3:06

I did some brute force computing and it looks like:

28 parked cars is indeed the best you can do

Here's 10 random solutions, where E represents an empty space:

 EE--E--
-E--E-E
-E--EEE
-E--E--
-E--E--
EEEEEEE
-------

EE-----
-EEEEEE
-E---E-
-EE--E-
-E---E-
-E-EEEE
-E-----

EE-----
-E-EEEE
-E---E-
-EE--E-
--E--E-
EEEEEE-
-----E-

EE-----
-E-EEEE
-E-E-E-
-E---E-
-E---E-
EEEEEE-
-----E-

E----E-
EEEE-E-
-E-EEE-
-E---E-
-E---E-
-E-EEEE
-E-----

E--E-E-
E--E-E-
EEEEEE-
-----E-
-----E-
EEEEEEE
-------

E------
EEEEEEE
-E-----
-E-----
-EEEEEE
-E-E-E-
-E---E-

E------
EEEEEEE
-----E-
-E--EE-
-E---E-
-EEEEEE
-E-----

E------
EEEEEEE
--E--E-
--E--E-
E-E--E-
EEEE-E-
-----E-

E----E-
EEEE-E-
-E-EEE-
-E-----
-E----E
EEEEEEE
-------

There's apparently 934 total optimal solutions, which seems so small that I wonder if I missed something. I definitely missed solutions like JonMark Perry's - solutions with islands of missing parking spaces. I didn't include these in the count, but I did double check that including them didn't yield better results.

• Can you prove that 28 is the best? – user35295 Oct 13 '17 at 4:12
• @AllanCao It's mostly brute force, if that counts as proof. Of course I didn't explore all 2^49 boards. I only explored boards where all empty parking spaces were connected, and I pruned my search using A* and a heuristic. The heuristic being that adding an extra empty parking space will only net you 2 additional cars at best. As for solutions with islands - I just took all the incomplete parking lots I was building up and filled in the holes. No better solutions there. No mathy proofs from me, sadly. At best I could prove the correctness of my program. – Geoffrey Oct 13 '17 at 4:45
• No worries! That's fine. Someone else is bound to prove it. – user35295 Oct 13 '17 at 5:09

I got:

which is 28, and has no extension via white space.

• It looks like a trivial re-arrangement of Alpha's solution. – user19641 Oct 12 '17 at 20:43
• But your arrangement clearly spells "19" on it, not 28 =p – justhalf Oct 14 '17 at 13:21

Here's a very important variable. You never stated how large the cars are or whether their dimensions are 1x1, 1x2,... etc. Once this information is provided, I'm certain I can give you an answer.

• I don't think the arrangement you give works (assuming I'm interpreting it correctly). The exit is in the top-left corner (1,1). The cars at (1,2) and (2,1) are blocking any of the other cars from accessing the exit. (As cars cannot move diagonally.) – R.M. Oct 12 '17 at 22:40
• From the question, you should have realized that cars should take up only one square? but I guess you didn't so, I would like to make it clear that every car takes up ONE square and ONLY one square! – user35295 Oct 13 '17 at 0:16
• Ugh -1 since a) it blocks the exit and b) how does having larger cars help you "fit more cars" (per the OP's question). – Tas Oct 13 '17 at 0:32