First, consider that O(*n*^{2}) is necessarily the worst case,
so if we show that the easiest of these cases is O(*n*^{2}),
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(*n*^{2}) 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(*n*^{2}).
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(*n*^{2}).

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.