# The Greenhouse Problem

While I was playing a certain popular indie farming game, I came across a dilemma. I have a greenhouse that I'd like to fill as efficiently as possible. How many plants can I fit in the greenhouse?

Rules:

• The greenhouse floor is made of tiles arranged in a 9x11 rectangle. The door is on the center of the 11-length edge.
• Each plant takes up 1 tile.
• Each plant needs to be watered by a sprinkler. Each sprinkler waters a 5x5 square around it.
• A plant and a sprinkler cannot be placed on the same tile.
• I must be able to reach every plant orthogonally. I cannot walk on plants or sprinklers. I can only move orthogonally.
• Asymmetry is allowed. The fewer sprinklers, the better, but there's no limit.

Here's an example with 46 plants:

S P P P P S P P P P S
P . . . . . . . . . P
. P P P P . P P P P .
P . . . . . . . . . P        . = empty
. P P P P . P P P P .        P = plant
P . . . . . . . . . P        S = sprinkler
S P P P S . S P P P S        E = entrance
P . . . . . . . . . P        ^
. P P P P . P P P P .       PSE :)
E

• Is it Stardew Valley? :P – iBug Feb 1 at 18:29

Here's a solution with

57 plants:

$$\begin{matrix} &S &P &P &P &P &P &P &P &P &P &P\\ &P &. &. &. &. &. &. &. &. &. &.\\ &P &. &P &S &P &P &P &P &S &P &P\\ &P &. &P &P &P &P &P &P &P &P &P\\ &P &. &. &. &. &. &. &. &. &. &.\\ &S &P &P &P &P &. &P &P &P &P &P\\ &P &P &S &P &P &. &P &P &S &P &P\\ &. &. &. &. &. &. &. &. &. &. &.\\ &P &P &P &P &P &. &P &P &P &P &P\\\end{matrix}$$

• Nice (ab)use of the rules, since we don't need to reach all sprinklers. – Bubbler Feb 1 at 6:31
• Yes, the 46 example does that, too. – RobPratt Feb 1 at 6:34
• Is this optimal? – Dmitry Kamenetsky Feb 1 at 12:25
• Oh, wow! The best design I could come up with only had 52 plants. This is amazing! – Nilster Feb 1 at 15:21
• @DmitryKamenetsky The best bounds I have are $[57,65]$. – RobPratt Feb 1 at 18:31

A perfectly symmetrical layout can achieve

56 plants

in this way:

P P P P P . P P P P P
. . . . . . . . . . .
P P S P P . P P S P P
P P P P P . P P P P P
. . . . . . . . . . .
P P P P P . P P P P P
P P S P P . P P S P P
. . . . . . . . . . .
P P P P P . P P P P P

I think this is near-optimal if not already optimal, because

this uses minimal amount of horizontal hallways that allow accessing all plants, and minimal amount of sprinklers for such a layout.

• If I could mark both as correct, I would! RobPratt's solution just barely edges out yours, but for the sake of aesthetic, I'm going to use this solution. Thank you! – Nilster Feb 1 at 15:19
• This is optimal if symmetry with respect to the middle column is imposed. – RobPratt Feb 1 at 18:30

Well I was going to do work today, but I had to abandon that plan when I saw this awesome problem :)

I wrote a heuristic solver that found multiple ways to obtain

57 plants

 S P P P P P P P P P S
P . . . . . . . . . P
P . P P P S P P P . P
P . P P P P P P P . P
P . S . . . . . . . P
P . P P P P P P P P S
P . P P P S P P P P P
P . . . . . . . . . .
S P P P P . P P S P P

or

P P P P P P P P P P S
. . . . . . . . . . P
P P S P P P P S P . P
S P P P P P P P P . P
P . . . . . . . . . P
P . P P P P P P P P S
P . P P S P P P S P P
P . . . . . . . . . .
S P P P P . P P P P P


I am pretty sure this is optimal, because almost every run obtained this many plants and no run obtained more plants.

An upper bound for the most plants an optimal solution can have is 62.

## 64 plants is impossible

A solution with an odd number of plants 2n+1 or an even number of plants 2n must contain at least n empty spaces in order for all those plants to be reachable. (Put another way, if we have n empty spaces, all connected by other empty spaces to the entrance, the most plants we can reach is 2n+1.)

So if a solution with 64 plants exists, that solution must contain at least 32 empty spaces. Thus, such a solution must contain at most 3 sprinklers.

If 3 sprinklers are to water 64 plants, at least one of those sprinklers must water at least 21 plants*. However, any arrangement of 21 (or more) plants around a sprinkler must contain plants that are not reachable, even if we assume the arrangement is surrounded by reachable empty spaces**. Thus, no solution can have a sprinkler watering at least 21 plants, so a solution with 64 plants is impossible.

That any solution with more than 64 plants is also impossible is trivial.

## 63 plants is impossible

By our logic so far, a solution with 63 plants would require at least 31 empty spaces.

The 2n+1 maximum number of reachable plants can only be obtained if the n empty spaces form a straight line up from the entrance. But a 31-space straight line would not fit in our 9x11 greenhouse. In order to fit 31 connected empty spaces into the greenhouse, there must be some 'wasted potential': for example, for every "corner"

PPP
··P
P·P


that exists in our set, we can deduct 1 from the maximum number of plants the arrangement can reach. (T-junctions, crossroads, and four-squares are even more wasteful.)

I freely admit this is somewhat woolly, but my contention is that fitting 31 (or more) connected empty spaces into a 9x11 grid requires at least three points of wastage. (Note that, for instance, the longest possible path with only two corners contains 11+8+10 = 29 spaces, and this is ignoring the fact that path is highly suboptimal because of the greenhouse's edge.)

Thus, for n 31 or greater, the maximum number of reachable plants is 2n+1-3 = 2n-2, and so a 63 plant solution would require at least 33 empty spaces. This leaves at most 3 spaces for sprinklers, so once again we require at least 1 sprinkler to water 21 plants and we reach an impossibility.

### Extensions

Even this upper bound is quite loose: it underestimates the amount of wastage there will be, it doesn't account for empty spaces at the edge of the greenhouse not reaching new plants outside the greenhouse, and it doesn't account for the fact sprinkler blocks need to fit into the greenhouse and be reachable through/around each other.

*In fact, 22, but 21 saves time later

**Such a 5x5 block would contain 1 sprinkler (at its centre), 21 plants, and 3 empty spaces. An empty space on the exterior ring of the block will make at most 1 extra plant on the interior ring reachable. An empty space on the interior ring of the block will make at most 2 extra plants on the interior ring reachable. Since there must be at least 1 empty space on the exterior ring of the block in order for any of the interior ring of plants to be reachable, there are at least 6 plants on the interior ring of the block, and thus there is no way of making them all reachable.