Given a set of 256 colors I wish to create a 16 x 16 palette from these colors where the sum of all 4-connected differences between colors in minimal. Of course there are 256! different arrangements so brute force is not considered.
I tried using a greedy algorithm where I start with the color closest to black and proceed in a zig-zig diagonal fashion through the 16x16 grid inserting the closest unused color to the already inserted one or two neighbors. The following (crummy) palette was the result:
I used perceptual difference with a low-cost approximation using RGB. Of course the algorithm should be the same regardless of the difference metric.
I assume the optimal solution is (at least) NP-hard (I am not sure how a NP verifier would work so maybe this problem isn't even in NP). If not, let me know. Otherwise, good heuristic solutions are acceptable.