title: How to sort colors in two dimensions?
body: <p>I am currently working on a hobby project to automatically solve a puzzle from the popular mobile game <em>I Love Hue</em>. The game is available <a href="https://play.google.com/store/apps/details?id=com.zutgames.ilovehue&amp;hl=en" rel="noreferrer">here</a>.</p>
  
  <p>Basically, the whole premise of the game is that you're given a bunch of colored rectangular blocks organized in a grid. You can swap most of the blocks except for a few fixed blocks, which are marked by black dots. The object of the game is to swap the blocks around so you get a two-dimensional spectrum of color. The colors are sorted such that the color of each block is approximately the average of the colors around it. (Sorry, I don't know any color theory but there's probably a word for what I'm looking for.) Here's what a typical puzzle looks like:</p>
  
  <p><img src="https://i.stack.imgur.com/5x5Up.png" alt="img"></p>
  
  <p>I have already been able to take screenshots through adb, extract the RGB matrix from the blocks and mark which blocks are "fixed". I'm having trouble with the actual algorithmic part of this problem. </p>
  
  <p>Here's what I've done so far:</p>
  
  <ol>
  <li>Converting the RGB to HSV and sorting the colors by hue in a one-dimensional list. This gives me a spectrum, but I do not know how to convert this result into two dimensions. </li>
  <li>Leaving the colors in RGB and attempting to work with a singular color. There's probably some multivariable calculus I could do here, but the difficulty lies in the fact that some colors share one or more of their RGB values. It would be necessary to consider all three colors. </li>
  <li>Using Euclidean distance to find the distance between each pair of colors. I understand that the final goal is to have this distance to be the smallest among adjacent colors, but the two-dimensional grid is making this more difficult. </li>
  <li>Using Euclidean distance, I have developed a metric for how ideal a certain grid is by looking at the Euclidean distance of the colors of adjacent blocks. However, I cannot find an efficient algorithm that can figure out the swaps necessary to get to an ideal state. </li>
  </ol>