The Greenhouse Problem

Question

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

Answer 1

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}

Answer 2

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.

Answer 3

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.

Answer 4

Here is my integer programming formulation. Let binary variables $r_{ij}, s_{ij}, p_{ij}$ indicate whether the tile $(i,j)$ is reachable/a sprinkler/a plant accordingly.

The objective function is $\alpha \sum_{ij} s_{ij} -\sum_{ij} p_{ij}$. I set $\alpha$ sufficently small ($1/(mn)$), and when proving the upper bound of plant count, I set $\alpha=0$.

Since p,s,e are exclusive: $$ r_{ij}+p_{ij}+s_{ij} \leq 1 $$ it is $\leq$ because a tile could be empty but not reachable.

P needs R in neighborhood: $$ p_{ij} \leq \sum_{i',j' \in N(i,j)} r_{i'j'} $$ where $N(i,j)$ means the orthogonally neighborhood of $(i,j)$.

P needs S in 5x5 neighborhood: $$ p_{ij} \leq \sum_{i',j' \in F(i,j)} s_{i'j'} $$ where $F(i,j)$ means the 5x5 neighborhood of $(i,j)$.

With only constraints above, any empty tile could be R. Let binary variables $re_{ijd}$ ($d=U,D,L,R$ representing up, down, left, right) indicates whether tile $(i,j)$ "fetches" reachablility from its $d$ neighbor. So it is necessary for that neighbor to be R $$ re_{ijd} \leq r_{i'j'}, \quad (i',j') = step(i,j,d) $$

Every R except one needs reachability from others: $$ r_{ij} = \sum_d re_{ijd} \quad (i,j)\neq (i_0, j_0) $$

From a perspective of graph theory, it is actually a directed graph. The tiles are nodes and the neighboring relationship forms edges (arcs, to be accurate). We need to select a subset of nodes (with $r$) and a subset of edges (with $re$) which forms a tree, whose root is $(i_0, j_0)$, and every child node points to parent node. The above formulation only describes the graph structure, so there might be cycles in it (e.g. two adjacent tiles point to each other). Then it becomes subtour elimination problem in TSP in my opinion. The only difference is that we ought to forbid all cycles but in TSP we reserve the big cycles.

I forbid cycles with lazy constraints, whenever the solver yields an incumbent solution, it is easy to check and find cycles in it. Say I find a cycle $C=\{(i,j,d)\}$, I forbid it with $$ \sum_C re_{ijd} \leq |C|-1 $$ (I also generate the reversed cycle and forbid it too.)

That is all constraints of my model. It is able to return the same solution given by others in 2 minutes, and to prove the upper bound of plant count within 4 minutes (with $\alpha=0$).

Answer 5

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.}