Greedy solution:
All picking of blocks below should be done such that it adheres to the row constraints.
- Pick the closest block not already picked (say this is an A).
- Pick the closest non-A block (say this is an B).
- Pick the closest non-A, non-B (thus C) block.
- Record this distance.
- If there was a closer C in the same row as B, pick that C, along with the next closest B and record the distance.
- For more than 3 colors, you'd want to just pick the next closest B in a different row.
- Stop if the closest unpicked block is further than
bestDistanceSoFar/3
, otherwise repeat from 1. - Return the best distance.
For this I'd suggest having a sorted list for each colour.
I believe this is optimal, but why it would be requires some thought.
Preprocess:
You can remove all blocks in the same row as Lolo, as you mentioned, but also all blocks further from Lolo than another block of the same type in the same row, which is not a lot in this case, but still.
Additional note:
Given that you only have 3 colours, the running time of brute force will be O(n3), which is quite a lot less than the O(n!) or O(2n) of the TSP.
The obvious optimization to the brute force is to separate all the colours, which will result in a running time of O(n1n2n3) where ni is the amount of blocks with the i-th colour.