Given a square filled randomly with the numbers $1$ to $N$, for instance $$\begin{array}{cccc} 16 &12 & 9 & 1\\ 11 & 3 & 4 & 7\\ 2& 8 & 5&14\\ 6& 10& 15& 13 \end{array}$$
The task is to group these numbers into $N/2$ sets ($8$ in this case), with the following rules:
- a set can contain as many numbers as you want
- only adjacent numbers can be in the same set
Example: $8+5+14+7$ and $16$ on its own, would be allowed, but not $2+3$ or $2+4$.
Once the $N/2$ sets are formed, the score is the lowest sum of the numbers found in any of the sets formed. Example: the grouping $16+11$, $12+3$, $9+4$, $ 1+7$, $2+6$, etc would have a score of $8$.
Question: Find a strategy that finds the highest score.
Brute force works for this $4\times 4 $ square, but in practice we have more like $10\times 10$ squares or larger.
Some background: The problem is a stylized version of a problem that came up in the company I work for, concerning assigning workloads to collaborators. We use an algorithm that looks the lowest pairs of sets and tries to add to them.
Example: $3+4$ is the lowest pair, so this is the first set, followed by $1+7$, $2+6$, $8+5$, $9+(3+4)$, etc.