1
$\begingroup$

Context of Concrete Problem:

While I have run into similar problems in other games, this specific one is for the game Stardew Valley. You would like to make a farm involving a scarecrow and the lowest level of sprinklers placing minimal sprinklers in the interior of the scarecrow's range to maximize space for crops. All crops must be placed in the range of the scarecrow, but not all sprinklers.

Scarecrow Range

Radius 8 tiled circle with center tile covered.

Here, the brown tile represents the scarecrow, and the green tiles represent spaces available for crops.

Sprinkler Range

Radius 2 tiled circle with center tile covered.

Here, the blue tile represent the placement of the sprinkler, and the dark green tiles represent the watered tiles.

Simplifications

Notice the outermost edge of the shape can always be watered by sprinklers outside of the range of the scarecrow. Because we only want to minimize the number of sprinklers placed in the interior, we can ignore the outermost edge.

Further, the sprinklers can instead be thought of as just a cross, and the scarecrow can be thought of as a hole in the middle of the circle.

Simplified Problem

What is the smallest number of Shape A, needed to cover Shape B (where instances of Shape A may overlap and Shape A is allowed to cover tiles outside of Shape B). Though, in this case, do not think of placing the center of the cross outside of the green area of Shape B.

Shape A

Tiled cross of height 3 and width 3.

Shape B

Tiled circle of radius 7, with a single tile missing from the center.

Example of Easier Problems

Problem solved for tiled squares and diamonds of increasing size.

Attempts at Solution

While I have attempted to make a "coloring" of the larger shape to find patterns in the placements, the overlapping of the smaller shapes is giving me issues. I've found bounds for the minimum number of smaller shapes to larger shapes, for specific cases. For example, the largest square given in the examples, either has a minimum of 12 or 13; I was only able to find an example of 13, but I can't show that there is not a solution for 12 smaller shapes.

I eventually ran to create a script to solve these problems, but even switching to Rust for the speed increase and many simplifications (such as requiring a given number of sprinklers in each quarter of the circle) still leaves way to many possibilities to check exhaustively.

Final Note

Sorry if this question is too verbose, but I find it very difficult to explain. As stated, I happen to run into this exact kind of problem in many games that I play, and I have never been able to make any progress. Apart from the uses in the game, this problem has been fun to work on in general, so I hope that giving the context in the form of a game does not diminish its acceptability in anyway.

$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

You can solve this set cover problem via integer linear programming as follows. Let $S$ be the set of possible cells for sprinklers. For $(i,j)\in S$, let binary decision variable $x_{ij}$ indicate whether a sprinkler is placed in that cell. Let $R$ be the range to cover. The problem is to minimize $\sum_{(i,j)\in S} x_{ij}$ subject to $$\sum_{(i,j)\in S: |i-u|+|j-v| \le 1} x_{ij} \ge 1 \quad \text{for all $(u,v)\in R$}$$

For the $9 \times 9$ example, the minimum turns out to be $12$: enter image description here

For the $15 \times 15$ example, the minimum turns out to be $36$: enter image description here

For the $17 \times 17$ example, the minimum turns out to be $48$: enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .