Organizing felt tip pens: sorting items in a 2D grid by similarity of adjacent items

I've got a box of 80 felt tip pens for my kid, and it annoys me so much that they are not sorted.

I used to play a game called Blendoku on Android where you need to do just that: arrange colors in such a way that they form gradients, with nearby colors being the most similar:

It is easy and fun to organize colors in intersecting lines like a crossword. But with these sketch markers, I've got a full-fledged 2D grid. What makes it even worse, colors are not extracted from a uniform gradient.

This makes me unable to sort felt tip pens by intuition. I need to do it algorithmically!

Here's what I've got:

• Solid knowledge of JavaScript
• A flat array of color values of all pens
• A function distance(color1, color2) that shows how similar a color pair is. It returns a float between 0 and 100 where 0 means that colors are identical.

All I'm lacking is an algorithm.

A factorial of 80 is a number with 118 digits, which rules out brute forcing.

There might be ways to make brute forcing feasible:

• fix the position of a few pens (e. g. in corners) to reduce the number of possible combinations;
• drop branches that contain at least one pair of very dissimilar neighbours;
• stop after finding first satisfactory arrangement.

But I'm still lacking an actual algorithm even for than, not to mention a non-brute-forcey one.

PS Homework:

• Sorting a matrix by similarity -- no answers.
• Algorithm for optimal 2D color palette arrangement -- very similar question, no answers.
• How to sort colors in two dimensions? -- more than 50% of cells already contain correctly organized colors; unfamiliar programming language; the actual sorting solution is not explained.
• Sort Colour / Color Values -- single flat array.

from Organizing felt tip pens: sorting items in a 2D grid by similarity of adjacent items