'Companion Planting' Logic Puzzle - Is there an elegant solution?

Question

Problem: You're a vegetable gardener planning to plant out seedlings in a new garden bed, however your farmer's almanac has outlined a system of rules about what plants can and cannot be placed next to each other. Your job is to map out a garden bed/s that will provide the most benefits to the plants within.

Each Plant has 5 classes of companion plant associated with them, ranging from mutually beneficial plantings to stunting or being stunted by neighbour Plants.

For example, the rules for planting Carrots state;
i) Mutually beneficial to Tomatoes and Leeks..
ii ) Receives Benefits from Onions and Rosemary.
iii) Provides benefits to Peas and Radishes.
iv) Has growth stunted by Dill and Coriander.
v) Stunts growth of Parsnip.

While Tomatoes state:
i ) Mutually beneficial to Carrots and Asparagus.
ii ) Receives benefits from Basil and Mint.
iii ) Provides Benefit to Gooseberries and Coriander.
iv ) Is stunted by Leeks, Onions, Fennel and Cabbage.
v) Stunts growth of Corn.
---

Each plant has a 'sphere of influence' that encompasses all plants with 2 spaces of it - Left, Right, Up, Down, Diagonally - so benefits or detriments affect those plants within those spaces. A plant does not have any effect on itself.

Graphically; o is the Primary plant, all x's around that plant are influenced by that plant's companion rules, all _'s are unaffected.
__________________
| _ | _ | _ | _ | _ | _ | _ |
| _ | x | x | x | x | x | _ |
| _ | x | x | x | x | x | _ |
| _ | x | x | o | x | x | _ |
| _ | x | x | x | x | x | _ |
| _ | x | x | x | x | x | _ |
| _ | _ | _ | _ | _ | _ | _ |

Plants can be planted in rows, columns or clusters. There is a limit of 10 rows and 100 columns per plant bed. There are 50 sets of plants with associated rules (as per Carrots and Tomatoes above). No limit to number of Plant Beds. You are required to lay out the maximum number of types of plants with the highest benefit scores (i.e - not just alternating rows of Carrots and Tomatoes and ignoring everything else).

So that's the basics of the rules. This is obviously not a complete problem for solving - I'm not looking for a 'solution' as such, for that you'd need to know all 50 plants and rules etc. What I'm looking for is more of a theory or problem solving logic that will help me create a 'map' of these plants. While I know it's possible to brute-force an answer through 'seating chart mayhem', I'd like to believe there's a more elegant mathematical/logical solution, I'm guessing something kinda like a venn diagram meets a weighted decision matrix - but... cleaner.


Full disclosure; This is not a homework question or logic puzzle. I'm actually looking to begin Organic Market Gardening myself, but after years of working in marketing all of the useful high school and college maths that works for problems like these has been replaced by analytics formulae, acquisition rates and social network models. I had to reach down into the depths of my mind just to bring up SOHCAHTOA so I could build an angled garden frame.

What I'm saying is, Any and All help is appreciated before I start cutting up pictures of plants and adding little score discs of 2+, 1+, 0, -1, -2 on a grid while constantly consulting rules that occasionally almost contradict each other.

Thank you all immensely in advance.

Answer 1

I think the answer is probably no.

Here's a much simpler but related problem. You have just two kinds of plants, carrots and tomatoes, on a square grid. Each cell in the grid either prefers carrots (you score +1 for planting carrots there, -1 for planting tomatoes) or prefers tomatoes (other way around). Each adjacent pair of cells either prefers to have the same kind of plants (score +1 if same, -1 if different) or prefers to have different kinds (other way around). Your goal is to maximize your score. The end.

Well, this is the problem of "finding a ground state of a 2d Ising spin glass with an external field" and it's NP-hard, meaning that (1) no efficient way to solve it is known and (2) if you found an efficient way to solve it, that would enable you also to solve a huge variety of other problems for which no efficient solution is known. (Here "efficient" has a technical meaning, namely that for some $d$ the time it takes to find the solution for a problem instance of size $n$ grows no faster than $n^d$.)

The problem becomes efficiently soluble if we take away the per-cell preference between carrots and tomatoes (leaving only the "interactions") -- but becomes hard again if we now, as in your problem, allow closer-than-nearest-neighbour interactions, even if it's just "next-but-one neighbour".

This doesn't prove that your problem is hard, because there are still plenty of differences between your problem and this one. But it's suggestive.

Rather than cutting up pictures of plants, I would suggest doing this on a computer, which can try things out much faster than you can. The simplest thing would be to make it try lots of random configurations and choose whichever one does best. Next simplest would be: after picking a random configuration, repeatedly try making small simple changes (e.g., change just one plant, or maybe swap a neighbouring pair) until you can't find any that make things better. Next simplest (which might actually be simpler, because there might be software out there that already does lots of the work) would be something like simulated annealing.

Answer 2

I think there is a perfect solution to your specific query.

Knowing that there are overlaps of pros and cons (benefits/stunts and benefited by/stunted by) you can easily plan your garden.

I'll give an example of 5 plants :

+2 = Mutual benefits

+1 = Benefited By

0 = No Effect

-1 = Stunted By

-2 = Mutual Stunting

Plant A |+2 B|+1 C | 0 |+1 D|-1 E|-2 |

Plant B |+2 A|+1 | 0 C|+1 E|-1 D|-2 |

Plant C |+2 |+1 A | 0 C|+1 |-1 |-2 E|

Plant D |+2 E|+1 B | 0 |+1 C|-1 |-2 |

Plant E |+2 D|+1 | 0 |+1 B|-1 A|-2 C|

Instead of 10 rows and 100 columns, I'll use a smaller grid of 5 rows and 10 columns to demonstrate a layout

|C|C|A|A|B|B|E|E|D|D| C and E are outside of each others influence [-2]

|C|C|A|A|B|B|E|E|D|D| A and B are paired as they have [+2]

|C|C|A|A|B|B|E|E|D|D| E and D are paired as they have [+2]

|C|C|A|A|B|B|E|E|D|D| B is buffered by E [+1] from D [-1]

|C|C|A|A|B|B|E|E|D|D| C gets no benefit from D [+1]

Should we increase the grid to 12x5 to demonstrate the repetitive pattern, then C does benefit from D [+1]

|C|C|A|A|B|B|E|E|D|D|C|C|.

Note: Your crops are aligned for optimum growth and ease of harvest. The numbers are arbitrary for demonstration purposes as plants also have different requirements such as water, temperature, season, etc.

Should you increase the number of plants and the benefit/stunt variables, you'll be looking at a different chart ;)

Regardless of what the variables are, you will need to group your beds according to the different requirements above, so you already have predefined sets which you are restricted to when formulating your tables.

A cluster structure using the same settings would look something like this:

|C|C|C|C|C|C|C|C|C|C|C|C|

|C|C|A|A|A|A|A|A|A|A|C|C|

|C|C|A|A|A|A|A|A|A|A|C|C|

|C|C|A|A|B|B|B|B|A|A|C|C|

|C|C|A|B|B|B|B|B|A|A|C|C|

|C|C|A|B|B|B|B|B|A|A|C|C|

|C|C|A|B|B|B|B|B|A|A|C|C|

|C|C|A|A|A|A|A|A|A|A|C|C|

|C|C|A|A|A|A|A|A|A|A|C|C|

|C|C|C|C|C|C|C|C|C|C|C|C|

Hope this helps.

I would like some literature regarding your almanac. Could you point me in the right direction?

Answer 3

As Gareth McCaughan says, there probably isn't a good method to solve this problem.
However, you might be able to find a sufficient solution by using so-called evolutionary algorithms (or other algorithms with the same principles). For example, by randomly swapping crops each generation you obtain either a better or worse crop-layout and by doing this multiple times can increase your overall score.
The algorithm would not need to brute-force all possible solutions, but might find a nice solution in reasonable time.
Also you would probably be able to set it up in less then an hour if you have experience with evolutionary algorithms.

Answer 4

You don't provide quite enough info-- you say that you are required to layout the maximum number of types with the maximum benefit, but you need to specify more. For example, of the 50 types, if some, say 5, have more detrimental effects, can you ignore or minimize those? If you have to plant all 50, do they have to be in equal numbers? If so, then it's a somewhat simpler problem. Similarly, if you could pick only the best 50%, that would also be simpler.

If there were no minimum requirements, you could do it recursively-- start with one, then randomly select from the most beneficial neighbors, move along, repeat. If there were more minimum requirements, you could track the total number of each type planted, and use that to weight the values of potential neighbors, so that eventually types not planted would have scores high enough. That is, the higher percentage of the total a type had, the lower the relevance of its benefit.