It helps that they used bags; because if all snippets were in one bag, then combinatorially, things would be much more difficult.

n pieces residing in the same b_i, i<16501 bags can be viewed as a blocking function in record linkage. That means while comparisons are O(N^2), here N=16500 and not N=i*16500. In practice, filtering by compatible color (effectively a 2nd-level blocking function) prunes the search space further.

The simplifying heuristic (works not always, but most of the time): "assume that all snippets belong to the same bag".

One important question is how big the individual snippets are - ideally, they'd contain fractions of more than one line of text on top of each other. According to @Pebblebox (see below), “Each bag contains between 2,500 and 3,500 fragments of torn-up pages.”, which means the fragments must be large enough on average to be amenable to language model application.

Then I'd create a data structure with the color of a snippet and its lines of text (either full lines, or prefixes and suffixes at the [left/right] fringes):

  type snippet_type = record
                        snippet_color: RGBColor;
                        text_height:   integer;
                        text:          lines[1..5] of record
                                                        left:  string;
                                                        right: string
                                                      end
                      end;

A statistical or neural language model should be able to piece individual pieces together and come up with a list (sorted by likelihood) of locally probable solutions (called "trellis" or "sausage" in ASR parlance), which can be combined using a beam search.

New captcha challenge?

That’s an odd price. Not knowing what a “bag” means, I think 13-gallon (“kitchen”) or larger lawn clippings bag is possible.

I wouldn’t for €100 sign up to scan even an office wastebasket (6-8 gallon) bag of torn-up paper. Make it €2000 for that quantity, and we’ll start talking.