Stitch a picture

Question

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 code-golf 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: