## September 2014 riddle

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, in both its original and simplified form, will continue to run in parallel with a new October riddle.

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 in the average case when their degree is assumed to be bounded. Specifically, you are asked to give tight upper and lower bounds for the average-case solution complexity of any family of bounded degree puzzles.

For completeness: the average-case solution complexity is the complexity, as a function of the number of tiles, of the expected number of tile match attempts one requires in order to determine unambiguously which tiles map to which positions. You are to assume that the optimal strategy is used (i.e., the strategy that minimises this expected value) and that the actual mapping is a random variable uniformly distributed between all n! possible mappings.