title: Issues with simple algorithm for automatic assembly of jigsaw puzzles (with rectangular tiles) in Swing
body: <p>I needed to design solver for puzzle, that is splitted in rectangular tiles (several rows and columns) with:</p>
  <pre><code>          BufferedImage subImage = 
            image.getSubimage(y, x, dWidth, dHeight) 
  
   
  </code></pre>
  <p>then resized with some ratio &lt; 1.0:</p>
  <pre><code>BufferedImage resized = new BufferedImage(newWidth, newHeight, original.getType());
  </code></pre>
  <p>The idea behind my algorithm is to sum the difference between every appropriate pixels of current tile side and all other opposite tiles sides -
  for example for right edge - I define such code:</p>
  <pre><code>for(Side s:reverseSides) { ...
  {for(int i=0;i&lt;height;i++) //checking current tile's right side
  int rgbValue1=image.getRGB(width-1,i); //right side rgb values of current tile
  int rgbValue2=imageN.getRGB(0,i); //left side rgb values of other tiles
  ....
  int diff=|rgbValue1-rgbValue2|;
  sum+=diff;
  }
  }
  </code></pre>
  <ul>
  <li><p>According to some algorithm, I start with some side whose sum of
  rgbvalues is in the very midth of the whole range of such sums of all
  sides (sortinglistBySum/2). Then I find minimal sum for with all
  opposites sides, and traverse all other 3 sides of this Tile, then go
  for Tiles, that has at least one already processed side, stored in
  queue untill all sides are processed in consecutive fashion.</p>
  </li>
  <li><p>But first big issue, not expected, is in that this minimal sum for
  about 80 pixels (in width or height) is around 50-70 000 000
  units(RGB), when maximal could be more over 1000 000 000. So this
  minimal sum, and even one difference for example first/second/Npixel
  getRGB(width-1,1) - getRGB(0,1) -- is big enough. Indeed before splitting -
  the difference between pixel position in adjacent edges
  should be just 1 pixel??</p>
  </li>
  <li><p>So, in this case if left tile &quot;right edge index&quot; width-1=80, then 0
  index in matching left side of right tile should be 81. Or at least
  difference could be 2- if one vertical pixel line is lost when image
  is splitted, and division of image width by number of columns does
  not produce integer value (I suppose that it is not real image so no
  pixels should be lost technically, just mathematically).</p>
  </li>
  <li><p>But when I calculate sum of diff. of two adjacent vertical (or
  horizontal) lines of pixels in one tile - getRGB(width-2,i) -
  getRGB(width-1,i) - it produce far lower values - some about 5-7 000
  000. getRGB(width-3,i) - getRGB(width-1,i) - 30-40 000 000. So I do not undestand why such big difference between adjacent pixels sets of
  original image?</p>
  </li>
  <li><p>The another issue is that when I found reverse side with minimal
  difference I check minimal sum of difference for this opposite side
  with reverse sides for it - and only if there is mutual match of sum
  of diff. I define these sides as adjacent, also restricted if this
  common minimal sum are less then some threshhold value defined
  empirically by myself - in my case I suppose it about 150 000 000
  (RGB diff.), but it is just approximation.</p>
  </li>
  <li><p>But there is third, probably most difficult issue - how check if this
  matched side(s) is not edge side of the whole image, even there is
  mutual match of sums, and less then threshold but in practice these
  sides should not be matched as they are not adjacent in original
  picture?!</p>
  </li>
  <li><p>This approach works relatively fine, except a lot of aspects to take
  into account, as well as difficulties of moving and changing grid
  cells in Java Swing layout.For example matching of the &quot;single edge&quot;
  issue happened in my third testing image, in one of the last
  iteration, but it could happened also at the start.Threshold value is
  in some infrequent cases above for no-mathcing sides (that indeed
  mutually matched with minimal sums), or under the really matching
  sides.</p>
  </li>
  </ul>
  <p>So what are suggestions and references for simple assured
  algorithms, what more reliable edges checking and patterns to use? Why so big sum of difference of rgb values of adjacent sides??
  I have read even before, that it should sum difference of square rgb values, but what it changes? Also read suggestions to have some statistically based algorithm so probably check all combinations - checking combination of edge traversing from every present edge (not just one) and then choose optimal combination.</p>