What combinatorial explosion? Unless you have a specially constructed jigsaw puzzle, in a jigsaw puzzle, every side of every piece fits only one other piece (unless the side is on the border). For most jigsaws, determining whether two pieces fit doesn't even require looking at the pictures, just determining wether the pieces lock, and if they do, whether their corners align is enough.

Considering there's only O(N²) pairs of pieces, with at most 16 ways for two pieces to possibly lock, this leads to a simply quadratic algorithm.

Of course, that still leads to the problem of determining whether two pieces match, but there's no combinatorial explosion. A combinatorial explosion would happen if you first assemble all (or a fraction of all) the pieces before you determine "match" or "no match".