What Is the Big-O Order of a Jigsaw Puzzle?

Let's say I have a jigsaw puzzle with n pieces? If you get no help from the picture (maybe it's completely white or something), then is the complexity O(n!), because I have to see if I can join every piece to every other?

But it's not just a linear array. It's a rectangle (or perhaps square). So if it's a square (of size m * m, where m = sqrt(n)), how does that change the complexity?

And then you have the border, of size 4m. At least those pieces you can identify (unless some interior pieces have straight edges, which happens in some puzzles). How does that change the complexity?

And then you have the picture. This gives you far more information. If nothing else, it lets you sort the pieces into buckets, based on what is pictured on them. So in practice, what's the actual complexity? Is it something like O(n^2)?

Surely there must be some literature on this. Does anyone know?