UPDATE (1 October): No correct solutions have been submitted so
far to this riddle. The riddle will therefore run one extra month. However, this
time credit will be given both to solvers of the original question and to
solvers of the following simplified riddle: "using the optimal strategy,
what is the complexity of the smallest expected number of comparisons needed to
solve a shape-sorting puzzle with n shapes (rather than a jigsaw puzzle
with n tiles)?" A shape-sorting puzzle is a
children's toy where holes of various shapes need to be matched by pegs of
matching shapes. A comparison is made when a particular peg's shape is
compared against a particular hole's shape.
This riddle continues on the theme of jigsaw puzzles from the October 2007 and July 2014 riddles. The set-up of what a jigsaw puzzle is and what solving it means has been described in these two previous riddles (more succinctly in the July 2014 riddle) and will not be repeated here. Briefly, the earlier riddle asks about how difficult it is, in the worst case, to solve a puzzle when its degree is assumed to be bounded. The latter does the same without the degree bound.
This month, we return to the world of jigsaw puzzles and ask how difficult it
is to solve them
For completeness: the average-case solution complexity is the complexity, as
a function of the number of tiles, of the As usual: prove your answer. |
## List of solvers: |

Elegant and original solutions can be submitted to the puzzlemaster at __riddlesbrand.scso.com__.
Names of solvers will be posted on this page. Notify if you don't want
your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!