NOTE: This question is currently in the SANDBOX. Please bear this in mind before adding new answers.

I have a large collection of fine art. My toddler is learning to use scissors and glue; lately she has started playing with my art collection. Fortunately she is really quite good with the scissors and cuts things up into perfect squares. She then uses glue to randomly tile the cut-up squares back into a new piece of art. For example, she reinterpreted my Mona Lisa (which wikipedia kindly hosts for me) as follows:

The following python script simulates what my toddler has done:

#!/usr/bin/python

import sys
import random
from PIL import Image

origname = sys.argv[1]

im = Image.open(origname)
width, height = im.size
width = (int(width + 99) / 100) * 100
height = (int(height + 99) / 100) * 100

im = im.crop((0, 0, width, height))

im2 = Image.new("RGB", (width, height), "black")

blocks = []
for x in range(width / 100):
for y in range(height / 100):
blocks.append(im.crop((x * 100, y * 100, (x + 1) * 100, (y + 1) * 100)))

random.shuffle(blocks)

for x in range(width / 100):
for y in range(height / 100):
im2.paste(blocks.pop().rotate(90 * random.randint(0,3)), (x * 100, y * 100))

im2.save("shuf" + origname)

Please excuse python skills - I'm still learning, but was happy to see how quick and easy it was to write this script. Polite code-reviews will be graciously accepted ;-)

It does the following:

• loads the image whose file name was given as a command-line parameter
• pads that image with black pixels such that the width and height are exactly divisible by 100
• divides the image into 100x100 pixel blocks
• randomly shuffles the blocks
• randomly rotates the blocks (by multiples of 90 degrees)
• reassembles the randomly arranged blocks back into a new image with the same size attributes as the (padded) original
• saves the new image using the original filename prefixed with shuf

Your task is to write a program that takes the output of this script, analyses the edges of each 100x100 block and reassembles them back to the original picture.

Input:

• an image filename. This may be passed at the commandline, via STDIN or even hard-coded, whichever is most convenient.

Output:

• either output the a singular rearranged image to a differnent file, or display the singular rearranged output to the screen.

Input and output specs are intended to be lenient here, as filename-parsing is a non-goal of this question.

Other rules

• The program must be able to correctly reassemble any random arrangement of the wikipedia Mona Lisa by the python script. Hard-coding of block transformations of the example image above is strictly not allowed.

• Because all 100x100 pixel blocks are randomly rotated, the output image may also be randomly rotated by a multiple of 90 degrees.

• It is understood that for some degenerate cases (e.g. chequerboard of 100x100) blocks it is impossible to correctly rearrange the image. In those cases it is acceptable to produce incorrect/undefined output. However I think in general for photo images and almost all "famous" artworks, reassembly should be possible. Works by Mark Rothko are a possible exception.

• Common image manipulation libraries may be used (e.g. Python's PIL), but any APIs expressly designed for this purpose are strictly banned.

• Standard “loopholes” which are no longer funny

Now my toddler got a hold of The Scream. This is the result that needs to be fixed:

• You can improve your Python code by removing all spaces, giving variables single-letter names, using exec with string replacement on the repetitive bits, and replacing (x + 1) * 100 with -~x*100. :-P
– xnor
Commented Oct 5, 2014 at 19:50
• This task is impossible. Sure you can try and minimize MSE on the edges and push it through greedy or the Hungarian algorithm, but its still fundamentally just a 'best guess' for the programmer's definition of 'best'. For any algorithm, you can craft input that defeats it. And images like this one robertnyman.com/images/0611/lightroom/… will, with 100x100 grids, defeat all attempts.
– Will
Commented Oct 7, 2014 at 11:52
• Maybe you should turn this into a code-challenge and make the score the number of correctly aligned edges (code size being the tie breaker). And it would be huge help if you used a lossless image format. Commented Oct 15, 2014 at 10:37
• This really sounds intresting/challenging but I think it might be too challenging. I tried for the mona lisa various distance metrics and calculated MSE for a lot of rotated/swapped tiles of the original mona lisa, and was always able to find configurations that had a lower global MSE than the original image. I am going to try some totally different approach now, but I think the idea is good to transform this into some "best out of 10 images" alignment contest like others suggested. Commented Oct 22, 2014 at 10:26
• This exact problem is an active area of research, see eg cs.umanitoba.ca/~ywang/papers/crv13_jigsaw.pdf and github.com/typeinference/jigsaw-puzzle which has an implementation of that. State of the art is just 96% correct; the paper also explains how it calculates that score (hint hint) Commented Oct 24, 2014 at 2:48