If you have more images solved , you can create a graph of RGB plots
plot a 3D graph, where x,y is the pixel position, and z is the color channel (R, G, or B). From it you can define some properties of gradients. If the graph is a plane than all you need is just normal (taken from 3 known cells). If this is a curved surface, depending on how many infections it received, you can determine how a large polynomial was used for it. From all this, you can start to solve it.
I would start with something simple (assuming not too large spaces or fancy polynomials):
Process each color channel separately. I would use only static tiles and interpolate the grid colors only from them. Something like:
Without seeing the graphs of R, G, B , I can not evaluate what kind of interpolation you need. If the graphs are linear, use bilinear or linear interpolation. If you do not use higher polynomials.
So, fill in all the grid cells that you can (have neighbors with a known color). After that, find the closest moving tile to the calculated color (if the cell has all 3 interpolated channels) and place them (and set them as static).
Now just repeat the process until all cells are calculated.
[Edit1 Dec 14 2017] some additional notes and more
It was curious and some time passed, so I gave him a chance. First I create a game in C ++ / VCL that takes your image as input (cropped and resized). Then I sorted the fragments manually and plotted the graphs:
White dots mean that the tile is installed correctly (corresponds to the interpolated color). The colored circles around the dots are interpolated colors (for visual comparison you need to enlarge to see them).
As you can see, the graphs of R, G, B 3D look linear, so (bi) linear interpolation should be sufficient.
If I tried only linear interpolation for strings, then the solver immediately solves the puzzle. However, when I encoded the same thing for columns (more unknown cells between the known ones), the solver began to make several incorrect placements (all material invalid, therefore, incorrect white dots).
I also tried HSL , but after a while I throw it away due to a wall hit, because the Hue can cross degrees 0 and 360 at any point that is no different from cases that did not overlap. To do this, he will need some heuristics or cross-correlation from neighboring allowed areas, and this will be too much coding for my taste. Without it, results are worse than when using RGB .
So, now I’m thinking about using bilinear interpolation or first allowing interpolation to short distances, and then solving the rest ...
[Edit2 Dec 14 2017] bilinear interpolation
It seems that bilinear RGB interpolation solves all the problems. Therefore, if your board is closed with fixed cells, it should work. If not, you need to solve this problem iteratively, and then use the newly allowed cells as a new binding to unresolved areas. I also realized that I have RGB , and I also repaired it :).
Here is the C ++ / VCL source for the game (it is not optimized at all):
This is one form application in BDS2006 with one 40 ms timer on it. So just add events ... You can ignore VCL visualization and window files. The important thing is that it has a class and a solve() function. It is used both for the correct verification of the placement and for the solution (depending on the _solve bool). This is the input image map.bmp
I did not encode the corresponding save / load functions, instead, I decided to use a bitmap directly (a waste of space, but hardly enhances the code).
The card itself is a 2D 32bit DWORD array with the form SSBBGGRR hex , where SS is the flag of the cell (fixed / resolved / unresolved).
Here's a compiled demo with source code
Read readme.txt for more information. Here is the result after solving (pressing [S]):
As you can see (no), the circles vanish because the bilinearly interpolated color matches your input more closely.
The program expects a grid size of 7x9, image resolution does not matter. Color is selected from the midpoint of the cell (black dot) and slightly to the right (tile color)
To do this efficiently, you can do 2 things:
add / use list containing undisclosed cells
instead of itearting over the entire iteration map only through a list of unresolved cells.
convert T(N^2) searches for T((N^2)/2) in a triangular search
It is still O(N^2) , but the constant time is less.
use the 3D RGB LUT table
for large grids, you can create 32K 3D LUT entries to find the matching cell found in O(1) . Just convert RGB to 15-bit color and use
DWORD LUT[32][32][32];
where LUT[r][g][b]=row+(column<<16); This will let you know where each color is located. All unused colors are set to 0xFFFFFFFF . Here is an example of using this technique for a similar purpose:
Look for recolor[32][32][32] in the code ... A coarse 15-bit color may not be enough for this purpose, so it may take more bits, for example, 18 bits, which will result in 256 KB writing, which is still manageable.
Creating this LUT will take O(N) , but use and support is just O(1) time.