However, the next time you see a professionally-done photomosaic, take a moment and really look at it. Especially look at the sharp lines of contrast in the original image. If the mosaic draws from a large source of images, you'll find that you can follow the line through the source images themselves, not just between images. For instance, if you've got a sharp horizontal beige/blue line, you will find that the algorithm will pick up an image of a sunny desert day or something where the line for the horizon is approximately correct.

To do a quality job requires at least edge detection and some fuzzy matching of the primary edges of images, which also means you need to break the image down into more than just averages, you need to be counting the colors of segments of the images.

Nothing impossible about this, of course, it's just that it's an awful lot of work for a challenge like this, considering the stakes.