Consider jigsaw puzzle P. If its pieces are identically-shaped, is the difficulty of the puzzle greater or smaller than with a puzzle where pieces can only be fit into some of the others?

Claim. Differently-shaped pieces make a puzzle easier to solve.

---

Proof.

Consider a box P, where every piece p_i has an exact match with either two (for corner pieces), three (edge pieces), or four (internal pieces) other pieces P_match,i = {p_m} (so 2 ≤ |P_match,i| ≤ 4). Consider also those pieces P_imp,i = {p_j}, for which an imperfect match exists with p_i. There is a tolerance t_i ∈ T associated with each p_i, where t_i > z for some lower bound z. This tolerance expresses the probability of a piece matching any other piece, and is a function of the shape of its teeth and concavities.

The tolerance for any p_i in a puzzle with identically-shaped pieces is the limit as t_i → 1, since any piece can fit into any other piece. The size of the set of pieces with which p_i fits (|P_fit,i| = |P_match,i| + |P_imp,i|) is directly proportional to the tolerance for that piece, or |P_fit,i| = x|1 - t_i|, for some x ∈ ℜ: the lower the tolerance, the less likely p_i is to fit with any p_j, and thus there are fewer pieces with which it can have an imperfect fit. Note that P_imp,i varies with t_i, but P_match,i does not. Thus, as t_i → 0, |P_imp,i| → 0. If |P_imp,i| = 0, then the only p_m which fit p_i are the 2-4 pieces which are the correct neighbors.

Thus, the more similarly-shaped the pieces of a puzzle are, the more possible matches there are for any given piece, and the harder it is to find its correct neighboring pieces. QED.

Now, you may have noticed that this is not the most elegant proof out there. So I challenge you to write me a proof worth of the Book.

1/15/08: We have a winner! DTal, as you can see, has responded. Of course, there's still space for a runner-up if you can write a better mathematical proof than mine.

This completely ignores the human element, in both the act of creating and the act of solving a puzzle. There are two distinct methods of finding the correct piece: shape, and colour. A puzzle with regular pieces forces a potential solver to rely on colour and image characteristics such as lines, but is also utterly predictable. An irregularly carved puzzle need not, but it does have the potential for deliberate trickery.

Let me tell you about my dear grandmother. She's a puzzle-maker by trade, and she wields a mean jigsaw. She invariably sends us at least one of her puzzles for Christmas. Fiendishly difficult, they are quite idiosyncratic with distinctively loopy pieces and full of cunning traps. Because each piece is hand-cut on a jigsaw, no two are alike. Oftentimes, she'll carve a piece along a line of colour to make the neighboring one hard to find. I have also done puzzles of hers which seemed to have 5 corner pieces (one was a dummy), 3 corner pieces (one was disguised), and NO corner pieces (the puzzle, it transpired, was round). Algorithm THAT, Major!

Another thing to consider is that while the pieces themselves are not identical in an irregular puzzle, the elements that make up a piece (loops, curves, hooks, etc.) can still be quite quite common. Since the human eye is bad at gauging exact tolerances, the number of potential "fits" is astronomical. Furthermore, a non-regular piece gives no clue as to its correct orientation, so it may potentially fit in a much larger number of places. Putting constraints on the way a puzzle is made, as is is done with a regular puzzle, cannot possibly INCREASE its potential complexity, can it?

Really, having done both regular and irregular puzzles, I can personally testify that irregular puzzles are both considerably harder and much more engaging (though you are of course free to disagree). Irregular puzzles are a challenge, a gauntlet cast by the puzzle maker. If you've never done an irregular puzzle, I know a very good vendor in the New England area...

Also, do I see the word "pimp" in your writeup? Why yes, I think I do. Five times, no less.