我目前正在从事一个爱好项目，以自动解决流行的手机游戏 I Love Hue 中的谜题。游戏上线here .
基本上，游戏的整个前提是给你一堆排列在网格中的彩色矩形块。除了几个固定的块，你可以交换大部分块，这些块用黑点标记。游戏的目标是交换周围的块，以便获得二维的颜色光谱。颜色被排序，使得每个块的颜色大约是它周围颜色的平均值。 (对不起，我不知道任何颜色理论，但可能有一个词来说明我正在寻找的东西。)这是一个典型的谜题:
我已经能够通过 adb 截取屏幕截图，从块中提取 RGB 矩阵并标记哪些块是“固定的”。我在这个问题的实际算法部分遇到了麻烦。
这是我到目前为止所做的:
最佳答案
如果您有更多 solved可以创建 RGB 图形绘图的图像
所以绘制 3D 图哪里x,y是像素位置和 z检查颜色 channel (R、G 或 B)。从中您可以确定梯度的一些属性。如果绘图是一个平面，那么您所需要的只是正常的(取自 3 个已知单元格)。如果它是曲面，取决于它有多少拐点，您可以确定使用了多大的多项式。从这一切你可以开始解决这个问题。
我会从简单的事情开始 (假设没有太大的差距或花哨的多项式):
分别处理每个颜色 channel 。我只会使用静态图块并仅从它们插入网格颜色。类似于:
没有看到 R,G,B 我无法估计您需要哪种插值。如果图形是线性的，请使用双线性或线性插值。如果不使用更高次多项式。
因此，尽可能填充任何网格单元格(具有已知颜色的邻居)。在此之后找到最接近计算颜色的可移动平铺(如果单元格插入了所有 3 个 channel )并放置它们(并设置为静态)。
现在只需重复该过程，直到计算出所有单元格。
[Edit1 Dec 14 2017] 一些额外的笔记和内容
很好奇，今天有时间，所以我试了一下。首先，我在 C++/VCL 中创建游戏，将您的图像作为输入(裁剪和调整大小)。然后我手动对瓷砖进行排序并绘制图形:
白点表示瓷砖放置正确(匹配内插颜色)。点周围的彩色圆圈是内插颜色(为了进行视觉比较，您需要放大才能看到它们)。
如您所见 R,G,B 3D 图看起来是线性的，所以(双)线性插值应该足够了。
如果我仅尝试对行进行线性插值，则求解器会立即解决难题。但是，当我为列(已知列之间的更多未知单元格)编码相同的代码时，求解器开始进行一些不正确的放置(使整个内容无效，因此出现错误的白点)。
我也试过 HSL 但过了一会儿，我因为撞到墙而把它扔掉了，因为 色相 可以穿越
0和 360在任何一点上的程度都与没有交叉的情况没有区别。为此，它需要来自相邻已解决区域的一些启发式方法或互相关，这对于我的口味来说编码太多了。没有它，结果会比使用 更糟RGB .所以现在我正在考虑使用双线性插值或先解决短距离插值，然后再解决其余的......
[Edit2 Dec 14 2017] 双线性插值
看起来像双线性 RGB 插值解决了所有问题。因此，如果您的电路板附有固定单元，它应该可以工作。如果不是，您需要迭代求解板，然后使用新求解的单元格作为未求解区域的新边界。我也意识到我得到了 RGB 颠倒了所以我也修复了那个:)。
这里 C++/VCL 游戏源(根本没有优化):
//$$---- 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=(map[y][x])&255;
x1=x0+(x*r)+((y*c)>>8);
y1=y0 -((y*s)>>8);
bmp->Canvas->MoveTo(x1,y1);
bmp->Canvas->LineTo(x1,y1-z);
} x0=x1+5;
bmp->Canvas->Pen->Color=clGreen;
for (y=0;y<mys;y++)
for (x=0;x<mxs;x++)
{
z=(map[y][x]>>8)&255;
x1=x0+(x*r)+((y*c)>>8);
y1=y0 -((y*s)>>8);
bmp->Canvas->MoveTo(x1,y1);
bmp->Canvas->LineTo(x1,y1-z);
} x0=x1+5;
bmp->Canvas->Pen->Color=clBlue;
for (y=0;y<mys;y++)
for (x=0;x<mxs;x++)
{
z=(map[y][x]>>16)&255;
x1=x0+(x*r)+((y*c)>>8);
y1=y0 -((y*s)>>8);
bmp->Canvas->MoveTo(x1,y1);
bmp->Canvas->LineTo(x1,y1-z);
}
}
}
// Solver
void map_solve(bool _solve) // check for solved state and try to solve if _solve is true
{
_redraw=true;
const int _thr=10; // color comparison threshold
int x,y,x0,x1,y0,y1,xx,yy;
int r0,g0,b0,r,g,b;
int r1,g1,b1;
int r2,g2,b2;
int r3,g3,b3;
DWORD c;
// compute interpolated colors to imap (wanted solution)
for (x=0;x<mxs;x++)
for (y=0;y<mys;y++)
if (DWORD(map[y][x]&0xFF000000)!=_ILoveHue_state_fixed)
{
for (x0=-1,xx=x;xx>= 0;xx--) if (DWORD(map[y][xx]&0xFF000000)==_ILoveHue_state_fixed){ x0=xx; break; }
for (x1=-1,xx=x;xx<mxs;xx++) if (DWORD(map[y][xx]&0xFF000000)==_ILoveHue_state_fixed){ x1=xx; break; }
for (y0=-1,yy=y;yy>= 0;yy--) if (DWORD(map[yy][x]&0xFF000000)==_ILoveHue_state_fixed){ y0=yy; break; }
for (y1=-1,yy=y;yy<mys;yy++) if (DWORD(map[yy][x]&0xFF000000)==_ILoveHue_state_fixed){ y1=yy; break; }
c=0;
if (int(x0|x1|y0|y1)>=0)
{
// bilinear interpolation
c=map[y0][x0]; r0=c&255; g0=(c>>8)&255; b0=(c>>16)&255;
c=map[y0][x1]; r1=c&255; g1=(c>>8)&255; b1=(c>>16)&255;
c=map[y1][x0]; r2=c&255; g2=(c>>8)&255; b2=(c>>16)&255;
c=map[y1][x1]; r3=c&255; g3=(c>>8)&255; b3=(c>>16)&255;
r0=r0+(r1-r0)*(x-x0)/(x1-x0);
g0=g0+(g1-g0)*(x-x0)/(x1-x0);
b0=b0+(b1-b0)*(x-x0)/(x1-x0);
r1=r2+(r3-r2)*(x-x0)/(x1-x0);
g1=g2+(g3-g2)*(x-x0)/(x1-x0);
b1=b2+(b3-b2)*(x-x0)/(x1-x0);
r =r0+(r1-r0)*(y-y0)/(y1-y0);
g =g0+(g1-g0)*(y-y0)/(y1-y0);
b =b0+(b1-b0)*(y-y0)/(y1-y0);
c=(r)+(g<<8)+(b<<16);
}
imap[y][x]=c;
}
// compute solved state
for (x=0;x<mxs;x++)
for (y=0;y<mys;y++)
if (DWORD(map[y][x]&0xFF000000)!=_ILoveHue_state_fixed)
{
map[y][x]&=0x00FFFFFF;
if (rgbdist(map[y][x],imap[y][x])<_thr) map[y][x]|=_ILoveHue_state_solved;
else map[y][x]|=_ILoveHue_state_unsolved;
}
// solver/checker
if (_solve)
{
// process all unsolved cells
for (x=0;x<mxs;x++)
for (y=0;y<mys;y++)
if (DWORD(map[y][x]&0xFF000000)==_ILoveHue_state_unsolved)
// find match in unsolved cells
for (xx=0;xx<mxs;xx++)
for (yy=0;yy<mys;yy++)
if (DWORD(map[yy][xx]&0xFF000000)==_ILoveHue_state_unsolved)
if (rgbdist(map[yy][xx],imap[y][x])<_thr)
{
// swap if found
c=map[yy][xx];
map[yy][xx]=map[y][x];
map[y][x]=(c&0x00FFFFFF)|_ILoveHue_state_solved;
}
}
}
} gam;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
{
gam.map_resize(7,9);
gam.bmp_load("map.bmp");
gam.map_solve(false);
_update=true;
ClientWidth=gam.sxs;
ClientHeight=gam.sys;
_update=false;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormDestroy(TObject *Sender)
{
gam.render_mode=_ILoveHue_render_board;
gam.draw();
gam.bmp->SaveToFile("map.bmp");
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender){ gam.draw(); Canvas->Draw(0,0,gam.bmp); }
void __fastcall TForm1::FormResize(TObject *Sender){ if (_update) return; gam.bmp_resize(ClientWidth,ClientHeight); }
void __fastcall TForm1::Timer1Timer(TObject *Sender){ if (gam._redraw) FormPaint(Sender); }
void __fastcall TForm1::FormMouseMove(TObject *Sender, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseUp(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
void __fastcall TForm1::FormMouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y){ gam.mouse(X,Y,Shift); }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormKeyDown(TObject *Sender, WORD &Key, TShiftState Shift)
{
if (Key=='S') gam.map_solve(true); // try to solve
if (Key=='M') { gam.render_mode^=1; gam._redraw=true; } // swap render modes
if (Key==115) gam.bmp->SaveToFile("screenshot.bmp"); // [F4] screenshot
}
//---------------------------------------------------------------------------
它是 BDS2006 中的单个表单应用程序，上面有单个 40ms 计时器。所以只需添加事件...您可以忽略 VCL 渲染和窗口内容。重要的是类和
solve()在其中发挥作用。它用于正确放置检查和求解(取决于 _solve bool)。这是输入图像 map .bmp 
我没有编写适当的保存/加载状态函数，而是选择直接使用位图本身(浪费空间但几乎没有代码工作)。
map 本身是二维 32 位
DWORD形式为 SSBBGGRR hex 的数组哪里SS是单元格的标志(固定/已解决/未解决)。这里用源代码编译了demo
阅读
readme.txt了解更多信息。这是求解后的结果(按 [S]):
由于双线性插值颜色与您的输入更匹配，因此您可以(不)看到圆圈消失。
程序期望大小为 7x9 的网格图像的分辨率并不重要。颜色从单元格的中点(黑点)和稍微向右(瓷砖颜色)采样
为了提高效率，您可以做两件事:
而不是遍历整个 map ，只遍历 Unresolved 单元格列表。
T(N^2)搜索到 T((N^2)/2)按三角形搜索 这还是
O(N^2)但是，恒定时间较小。 对于大网格，您可以创建 32K 个条目 3D LUT 表在
O(1) 中查找搜索到的匹配单元格.只需将 RGB 转换为 15 位颜色并使用DWORD LUT[32][32][32];
哪里
LUT[r][g][b]=row+(column<<16);通过这种方式，您将知道每种颜色的放置位置。所有未使用的颜色设置为 0xFFFFFFFF .这是将这种技术用于类似目的的示例:寻找
recolor[32][32][32]在代码中...粗略的 15 位颜色可能不足以达到此目的，因此您可能需要更多位，如 18 位，从而产生 256K 条目，但仍可管理。创建此 LUT 将采取
O(N)时间但使用和维护它只是O(1)时间。
关于arrays - 如何在二维中对颜色进行排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47760628/