Arranging Colors in a Grid; Two Dimensional TSP?
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.