I am working on an interesting problem, which I believe can be solved algorithmically. I have a 6×8 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.