arrays - How to sort colors in two dimensions?

Question

I am currently working on a hobby project to automatically solve a puzzle from the popular mobile game I Love Hue. The game is available here.

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:

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.

Here's what I've done so far:

1. 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.
2. 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.
3. 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.
4. 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.

Answer 1

If you have more solved images you could create RGB graphs plot

so plot the 3D graph where x,y is pixel position and z is inspected color channel (R,G or B). From it you can determine some properties of the gradients. If the plot is a plane than all you need is just the normal (taken from 3 known cells). If it is curved surface depending on how many inflex points it got you can determine how big polynomial was used for it. From all this you can start solving this.

I would start with something simple (assuming not too big gaps or fancy polynomials):

Handle each color channel separately. I would use just the static tiles and interpolate the grid colors only from them. Something similar to:

• Interpolating 3D Coordinates between known missing time intervals

Without seeing the R,G,B graphs I can not estimate which kind of interpolation you need. If the graphs are linear use bi-linear or linear interpolation. If not use higher degree polynomials.

So fill in any grid cells that you can (has neighbors with known color). After this find the closest movable tile to computed color (if cell has all 3 channels interpolated) and place them (and set as static).

Now just repeat the process until all the cells are computed.

[Edit1 Dec 14 2017] some additional notes and stuff

Was curious and got some time today so I gave it a shot. First I create the game in C++/VCL which took your image as input (cropped and resized). Then I sorted the tiles manually and plot the graphs:

The White dots means tile is placed correctly (match the interpolated color). The colored circles around the dots are the interpolated colors (for visual comparison you need to zoom to see them).

As you can see the R,G,B 3D plots looks linear so (bi)linear interpolation should be enough.

If I tried just linear interpolation for rows only the solver solves the puzzle immediately. However When I coded the same for columns (more unknown cells between known ones) the solver started to make few incorrect placings (invalidating the whole stuff hence the wrong white dots).

I Also tried HSL but after a while I throw it away due to hitting a wall because Hue can cross the 0 and 360 degree at any point which is not distinguishable from cases that did not cross. For that it would need some heuristics or cross correlation from neighboring solved areas and that would be too much coding for my taste. Without it the results where even worse then using RGB.

So now I am thinking about either using bilinear interpolation or solve the short distance interpolations first and only then solve the rest ...

[Edit2 Dec 14 2017] bilinear interpolation

Looks like bilinear RGB interpolation solves all the issues. So if your board is enclosed with fixed cells it should work. If not you need to solve the board iteratively and then use the newly solved cells as new bound for the unsolved areas. Also I realized I got RGB reversed so I also repaired that :).

Here the C++/VCL source for the game (It is not optimized at all):

//$$---- Form CPP ----
//---------------------------------------------------------------------------
#include <vcl.h>
#include <math.h>
#pragma hdrstop
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
//---------------------------------------------------------------------------
TForm1 *Form1;
bool _update=false;
//---------------------------------------------------------------------------
const _ILoveHue_state_fixed   =255<<24;
const _ILoveHue_state_unsolved=  0<<24;
const _ILoveHue_state_solved  =  1<<24;
const _ILoveHue_render_board=0;
const _ILoveHue_render_graph=1;
//---------------------------------------------------------------------------
int rgbdist(DWORD c0,DWORD c1)  // AABBGGRR
    {
    int r0,g0,b0,r1,g1,b1;
    r0=( c0     &255); r1=( c1     &255);
    g0=((c0>> 8)&255); g1=((c1>> 8)&255);
    b0=((c0>>16)&255); b1=((c1>>16)&255);
    r0-=r1; g0-=g1; b0-=b1;
    return (r0*r0)+(g0*g0)+(b0*b0);
    }
//---------------------------------------------------------------------------
class ILoveHue
    {
public:
    // variables
    bool _redraw;               // redraw needed?
    Graphics::TBitmap *bmp;     // screen buffer
    int sxs,sys,mxs,mys,gxs,gys;// screen,map,grid cell resolution
    DWORD **map,**imap;         // map[y][x] actual and interpolated
    int mx,my,mx0,my0;          // mouse position state actual and last
    TShiftState sh,sh0;         // mouse buttons and spec keys state actual and last
    int render_mode;
    // class constructors and destructors
    ILoveHue()  { bmp=new Graphics::TBitmap; bmp_resize(1,1); map=NULL; imap=NULL; mxs=0; mys=0; mx=-1; my=-1; mx0=-1; my0=-1; gxs=1; gys=1; render_mode=_ILoveHue_render_board; }
    ~ILoveHue() { map_free(); if (bmp) delete bmp; }
    ILoveHue(ILoveHue& a)   { *this=a; }
    ILoveHue* operator = (const ILoveHue *a) { *this=*a; return this; }
    //ILoveHue* operator = (const ILoveHue &a) { ...copy... return this; }

    // game/Window API and stuff
    void map_free()                             // relese map
        {
        if ( map) { if ( map[0]) delete[]  map[0]; delete[]  map; }  map=NULL; mxs=0; mys=0;
        if (imap) { if (imap[0]) delete[] imap[0]; delete[] imap; } imap=NULL;
        }
    void map_resize(int x,int y)                // resize/allocate map
        {
        _redraw=true;
        if ((x==mxs)&&(y==mys)) return; map_free();
         map=new DWORD*[y]; if ( map==NULL) return;  map[0]=new DWORD[x*y]; if ( map[0]==NULL) return;
        imap=new DWORD*[y]; if (imap==NULL) return; imap[0]=new DWORD[x*y]; if (imap[0]==NULL) return;
        mxs=x; mys=y; for (x=mxs,y=1;y<mys;y++,x+=mxs) { map[y]=map[0]+x; imap[y]=imap[0]+x; }
        if (mxs) gxs=sxs/mxs; else gxs=1;
        if (mys) gys=sys/mys; else gys=1;
        }
    void bmp_resize(int x=-1,int y=-1)          // resize bmp
        {
        _redraw=true;
        if ((x>=0)&&(y>=0)) bmp->SetSize(x,y);
        bmp->HandleType=bmDIB;
        bmp->PixelFormat=pf32bit;
        sxs=bmp->Width;
        sys=bmp->Height;
        if (mxs) gxs=sxs/mxs; else gxs=1;
        if (mys) gys=sys/mys; else gys=1;
        }
    void bmp_load(AnsiString file)              // init game from image (map must be resized already)
        {
        _redraw=true;
        // load file
        bmp->LoadFromFile(file);
        bmp_resize();
        // convert to map
        int x,y;
        DWORD *p,c;
        for (y=0;y<mys;y++)
         for (p=(DWORD*)bmp->ScanLine[(y*gys)+(gys>>1)],x=0;x<mxs;x++)
            {
            c=p[(x*gxs)+(gxs>>1)+4]&0x00FFFFFF;         // near mid point (0<<24 is unsolved state)
            c=((c>>16)&0x000000FF)                      // RGB -> BGR (file has reverse RGB order than bmp)
             |((c<<16)&0x00FF0000)
             |( c     &0x0000FF00);
            map[y][x]=c;
            c=p[(x*gxs)+(gxs>>1)]&0x00FFFFFF;           // mid point
            if ((((c)|(c>>8)|(c>>16))&255)<64)          // ~max(R,G,B)<32
             map[y][x]|=_ILoveHue_state_fixed;
            }
        }
    void mouse(int x,int y,TShiftState s)       // handle mouse
        {
        _redraw=true;
        mx=x/gxs;
        my=y/gys;
        sh0=sh; sh=s;
        bool q0=sh0.Contains(ssLeft);
        bool q1=sh .Contains(ssLeft);
        if ((!q0)&&( q1)){ mx0=mx; my0=my; }    // mouse left button down
        if (( q0)&&(!q1))                       // mouse left button up (swap)
            {
            // swap if valid coordinates
            if ((mx0>=0)&&(mx0<mxs)&&(my0>=0)&&(my0<mys)) if (DWORD(map[my0][mx0]&0xFF000000)!=_ILoveHue_state_fixed)
             if ((mx >=0)&&(mx <mxs)&&(my >=0)&&(my <mys)) if (DWORD(map[my ][mx ]&0xFF000000)!=_ILoveHue_state_fixed)
                {
                DWORD c=map[my0][mx0]; map[my0][mx0]=map[my][mx]; map[my][mx]=c;    // swap cells
                map[my0][mx0]&=0x00FFFFFF; map[my0][mx0]|=_ILoveHue_state_unsolved; // set them as unsolved
                map[my ][mx ]&=0x00FFFFFF; map[my ][mx ]|=_ILoveHue_state_unsolved;
                map_solve(false);                                                   // check for solved state
                }
            // clear selection
            mx0=-1; my0=-1;
            }
        }
    void draw()                                 // render game
        {
        _redraw=false;
        int x,y,z,x0,x1,x2,y0,y1,y2,r;
        DWORD c;
        if (render_mode==_ILoveHue_render_board)
            {
            for (y0=0,y1=gys,y2=gys>>1,y=0;y<mys;y++,y0+=gys,y1+=gys,y2+=gys)
             for (x0=0,x1=gxs,x2=gxs>>1,x=0;x<mxs;x++,x0+=gxs,x1+=gxs,x2+=gxs)
                {
                c=map[y][x];
                bmp->Canvas->Pen->Color=TColor(c&0x00FFFFFF);
                if ((x==mx )&&(y==my )) bmp->Canvas->Pen->Color=clYellow;
                if ((x==mx0)&&(y==my0)) bmp->Canvas->Pen->Color=clGreen;
                bmp->Canvas->Brush->Color=TColor(c&0x00FFFFFF);
                bmp->Canvas->Rectangle(x0,y0,x1,y1);

                if (DWORD(c&0xFF000000)!=_ILoveHue_state_fixed)
                    {
                    r=10;
                    bmp->Canvas->Pen->Color=imap[y][x]&0x00FFFFFF;
                    bmp->Canvas->Brush->Style=bsClear;
                    bmp->Canvas->Ellipse(x2-r,y2-r,x2+r,y2+r);
                    bmp->Canvas->Brush->Style=bsSolid;
                    }

                if (DWORD(c&0xFF000000)!=_ILoveHue_state_unsolved)
                    {
                    if (DWORD(c&0xFF000000)==_ILoveHue_state_fixed ) c=clBlack;
                    if (DWORD(c&0xFF000000)==_ILoveHue_state_solved) c=clWhite;
                    r=4;
                    bmp->Canvas->Pen->Color=c;
                    bmp->Canvas->Brush->Color=c;
                    bmp->Canvas->Ellipse(x2-r,y2-r,x2+r,y2+r);
                    }
                }
            }
        if (render_mode==_ILoveHue_render_graph)
            {
            bmp->Canvas->Pen->Color=clBlack;
            bmp->Canvas->Brush->Color=clBlack;
            bmp->Canvas->Rectangle(0,0,sxs,sys);
            r=13; x0=15; y0=sys-15;
            int c=r*double(256.0*cos(55.0*M_PI/180.0));
            int s=r*double(256.0*sin(55.0*M_PI/180.0));
            bmp->Canvas->Pen->Color=clRed;
            for (y=0;y<mys;y++)
             for (x=0;x<mxs;x++)
                {
                z=(