It can certainly not be any lower than *n* log *n*, because one
is trying to communicate here through the match/no-match yes/no answers the
identity of a bijection, one of *n*! possible outcomes. Even if we were
able to use *any* set of questions, rather than the set of tile-matching
questions we are restricted to, this cannot be done in less than
log(*n*!) bits of information, or log(*n*!) answers, which gives
the desired lower bound.

In order to show that it is not higher, we construct a specific *S* and
a specific strategy that attains O(*n* log *n*) over *S*.

We begin by describing *S*. We construct *S* over another set of
puzzles, *S*'. Let *S*' be any set of puzzles without self-symmetries
with an unbounded puzzle size.

We will now "expand" each element of *S*' into a new graph, and these
expanded graphs will be the elements of *S*. The expansion process is as
follows:

Let *k* be the original puzzle size, and let its vertices be
*R*_{1} through *R*_{k}. We add to the graph
another 2^{k}-1 vertices, which we label *L*_{1}
through *L*_{2k-1}. The *L* vertices are
not connected to each other, but they are connected to the *R* vertices
as follows. Each *L*_{i} is connected exactly to those
*R*_{j} for which the *j*'th position in the binary
representation of *i* is 1.

The resulting *S* is clearly unbounded in its size, as the size of each new
element is *n*=*k*+2^{k}-1. Let us prove that
each of its elements lacks self-symmetries: first, note that each *R*
vertex connects to at least 2^{k-1} vertices in the graph,
whereas *L* elements connect to at most *k*. With *k* having to
be at least 6 due to the original graph lacking self-symmetries,
these two groups are clearly distinguishable.
Within the *R* set, the vertices can be labelled uniquely, because their
subgraph is taken from *S*', which we assumed contains no self-symmetries.
Lastly, once the label of each *R*-vertex is known, the identity of each
*L* vertex can simply be read out in binary form based on which *R*
vertices it is connected to.

Let us now describe an algorithm that solves this jigsaw puzzle in
O(*n* log *n*) tile-match comparisons.

1: LetTbe the original set of tiles. 2:Bag←T. 3: WhileBag≠Ø: 4: Pickxarbitrarily fromBag. 5: Try to matchxwith every tile it hasn't been compared with, yet. 6: LetNbe the set of all ofx's neighbours. 7: If |N|≤k: //xis inL8:NewR←N. 9: Else: //xis inR10:NewR←{x}. 11: For eachrinNewR: 12: Try to matchrwith every tile it hasn't been compared with, yet. 13: Removerand all its neighbours fromBag.

Let us analyse this algorithm. First, note that each element in *L* has
at least one neighbour, so *NewR* is never empty. For this reason, we
know that *Bag* shrinks by at least one element in every iteration through
the loop of step 3. So, we know that the algorithm terminates.

Next, we know that for every *r* found -- that is, for every new element
found in *R* -- we remove at step 13 all elements in *Bag* that are
at distance at most 1 from it in the connectivity graph. Because the elements of
*NewR* are all at distance at most 1 from *x* (an element picked from
*Bag*) whether *NewR* was populated at step 8 or step 10, we know
that no element in *NewR* can ever be a previously-used *r* value.
The *r* values all belong to *R* and *R* is of size
*k*=O(log *n*), so the loop at step 11 can repeat in total at most
this many times. Because *NewR* is never empty, this number of iterations
is at least as large as the number of repetitions through the loop of step 3.
In total, we see that the number of times the algorithm passes through both
step 5 and step 12 is O(log *n*). At each of these steps, it makes at
most *n* comparisons, for a total of O(*n* log *n*), as
required.

Finally, note that if *Bag* is empty then, in particular, all elements
have been removed from *L*, which can only be done if they appeared as
neighbours of values of *r*. We claim that this means that every value in
*R* must have appeared as an *r* value. To see this, note that for
any *R*_{i} the element
*L*_{2i-1} is an element that connects only to
it. Its removal from *Bag* indicates that *R*_{i}
appeared as a value of *r*. So, we know that all elements of *R* have
been used as *r* values, and therefore every match between any element of
*R* and any other element has been tried. In our puzzle graph, there are no
edges between elements of *L*, so this indicates that every edge in the
graph has already been found. Because we know that the graph has no
self-symmetries, we know from this that the puzzle has been solved.

Q.E.D.