Arranging Colors in a Grid; Two Dimensional TSP? I am working on an interesting problem, which I believe can be solved algorithmically. I have a 6x8 on which I am attempting to arrange 48 color swatches, such that the transition from each swatch to its neighbor is as smooth as possible.

I can compute perceptual color differences using LAB-space encoding, so it is simple to generate a matrix of color differences. If I were attempting to simply order these colors, it would essentially be the traveling salesman problem; and I could use some heuristic solutions to get a near optimal result.

However, arranging the colors into a grid introduces a new dimension. In the interest of symmetry, we can wrap the edges of the grid so that each swatch has exactly 4 neighbors.

I have a hunch that this problem reduces to the following graph problem: Given a fully connected weighted graph of 48 nodes, find a subset of this graph such that the resulting graph is fully connected, each node has exactly 4 edges, and the sum of edge weights is minimized.

Any ideas on existing algorithms that might be helpful in solving this problem? Approximate solutions and heuristic solutions are acceptable as I imagine this problem is in EXP.
You can solve the problem with any solver for the Quadratic Assignment Problem (QAP). In the traditional QAP, facilities are assigned to locations such that the cost of transporting necessary goods between any two facilities is minimal. QAP is NP-hard.

Here we assign the colors $C$ to the swatches $S$. The weight or flow $w : S \times S$ between the locations is $1$ if they are neighbors and zero otherwise – you may define neighborhood however you like. The distance $d : C \times C$ would be LAB-metric you already defined.