# Algorithm for optimal rule-based arrangements?

I am trying to plant a row in a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as defined in this table(I have one of each):

Num Vegetable     Friends      Foes
1   Watermelon    7,4,3        8,6
2   Tomatoes      9,8,6,5,1    7
3   Sunflowers    7,6,11
4   Zucchini      9,7,3
5   Eggplant      9,6,2        7,10
6   Cucumbers     9,7,3        8,1
7   Corn          8,6,4,3,1    5,2
8   Cantaloup     7,4,3        6,1
9   Bell peppers  6,5,11,10,2
10  Swiss chard   2            5
11  Rhubarb       9,3


How do I find the arrangement? Sort them using an algorithm? The title was my best guess at the answer. I am trying to understand the thought process and the implementation.

• Watermelon 1's friends includes Zucchini 4 but Zuccihini 4's friends does not include Watermelon 1. Is that intentional? – John L. May 19 at 21:24
• I believe so. I got my information from From Seed To Spoon, and I think it means that watermelon benefits from zucchini, but zucchini does not particularly benefit from watermelon. – Sam May 19 at 21:27
• It happens all foes are mutual in the table. Interesting. – John L. May 19 at 21:30
• Most Constrained Variable and Least Constraining Values could be helpful. – John L. May 19 at 21:37

You can solve such a problem by simply iterating over all $$n!$$ different permutations, and checking each if any of the arrangements is allowed and how good it is. This has complexity $$O(n \cdot n!)$$.
Much faster (but still exponential complexity) will be a variation to the Bellman–Held–Karp algorithm. Compute for each pair $$(V, v)$$ with $$V$$ being a subset of all vegetables and and $$v \in V$$, if it is possible to arrange the vegetables $$V$$ in a way such that $$v$$ is the last one and what it's best value is. You can define a recursive formula for this function, and apply dynamic programming, like in the BHK algorithm. That should run in $$O(n^2 \cdot 2^n)$$.
Let $$G = (V,E)$$ be a graph. For each vertex $$u$$ create a vegetable that has no friends and has all vegetables corresponding to vertices in $$\{v : (u,v) \not\in E\}$$ as foes.
There is a way to plant all vegetables in a row with no adjacent foes if and only if there is a simple path of length $$|V|$$ in $$G$$, that is, if and only if there is an Hamiltonian path in $$G$$ .