First, consider that O(n2) is necessarily the worst case, so if we show that the easiest of these cases is O(n2), so must they all be. Certainly, by forcing the Oracle to answer "no" whenever two tiles do not fit (or one tile does not fit a proposed position) in the final construction, we are merely narrowing the options the Oracle, and that cannot make the worst-case any worse.
Second, we will show that the structure of the graph and the question of whether or not we have a guiding image are also immaterial. We will do so by considering what would have happened if we were able to force the Oracle into giving us certain additional details, something that surely does not make the problem any harder.
Specifically, let us choose from the n tiles n/(d+1) that are unconnected to each other. (This can be done by first picking one, then removing all its neighbors, then repeating the procedure until we have n/(d+1) tiles. Because no tile can remove more than d other tiles, we know that we can take at least this number.) We will now narrow our problem specifically to these (still O(n)) tiles, forcing the Oracle to give us all information it knows about the other tiles and all their pairings.
We are left with O(n) tiles which are guaranteed not to be connected among each other, and for which the information of whether they are connected to the other tiles or not is equivalent to the information of whether they fit in specific positions or not. In this constellation, the structure of the graph clearly has no further effect, and a query equivalent to "does this tile fit here?" is the only query at our disposal, whether or not the puzzle was originally pictorial. We say that the puzzle is solved after the Oracle answers "yes" to n/(d+1) different questions (that is, after all questions that have a "yes" answer have been asked).
We will show that for this reduced problem, there is still no solution in less than O(n2) queries.
For this purpose, let us first consider the following lemma:
Lemma: Any bipartite graph with n elements on each side where each element connects to at least half of the elements of the other side has a perfect matching.
To prove this, consider Hall's Marriage Theorem. In order to fit with the conditions of the theorem, we need to show that each subset with k elements (which can be restricted to subsets with all elements taken from the same side) has at least k neighbors.
In our case, if k≤n/2, the number of neighbors is at least n/2, because even the first element adds this number of neighbors. If k>n/2 the number of neighbors must equal n. The reason for this is that if even one of the n would have been missing, so must all its neighbors, of which there must be at least n/2, contradicting the previous claim. Either way, the conditions of the marriage theorem are met.
Returning to our jigsaw puzzle, consider the following algorithm, to be followed by the Oracle:
The Oracle maintains a list of tiles and positions that are currently unmatched, always keeping the following condition:
Condition: A tile can only be unmatched if it wasn't compared, yet, against more than half of the unmatched positions. A position can only be unmatched if it wasn't compared, yet, against more than half of the unmatched tiles.
The method in which the Oracle keeps this condition is that whenever a tile or a position violates the condition, it ceases to be "unmatched". For our purposes, when this happens, the Oracle can explicitly give the information of which tile/position pair is matched. (Forcing the Oracle to divulge more information than it has to certainly doesn't make the problem harder.) The Oracle, in this case, simply chooses a matching, M, (which the lemma guarantees exists) and gives the information for the tile/position pair being removed from the "unmatched" list according to this matching.
Note that removing the first pair may cause other tiles/positions to begin violating the condition. These are removed iteratively, until the condition is, again, met.
If the Oracle is asked a question that doesn't violate the condition, it simply answers "no".
When the "unmatched" list is empty, the puzzle is solved.
What remains to be shown is that this process, which is certainly no longer than the regular puzzle-solving process, is still O(n2). In order to do this, consider that each tile/position pair, before it was divulged by the Oracle, required of the solver at least k/2 queries, where k is the number of remaining unpaired tiles at this time. This means that as a minimum, the number of queries for solving the puzzle must have been 1/2+2/2+3/2+...+n/(d+1)/2, which is clearly O(n2).
Readers who are interested in this model of jigsaw puzzles are welcomed to
consider the follow-up question below:
Real
puzzle pieces don't just have a set of other tiles that they can connect to,
but, instead, must be connected to the other tiles in a particular arrangement.
A tile that connects to "A" on its north end and "B" on its west end
does not necessarily connect well to "A" on its west
end and "B" on its north end. It would seem that a model of jigsaw puzzles
incorporating these distinctions is a more general problem than the simple
"connected graph" jigsaw puzzle. The question is this: show that the two models
are equivalent in terms of the complexity of performing operations on them.