I drew one archetypal shape, then add random noise to the spline control points for each instance. That means, to get the results looking right, I had to tweak

I drew one archetypal shape, then add random noise to the spline control points for each instance. That means, to get the results looking right, I had to tweak the archetype, and the 2D noise variance, potentially separately for each point. I ended up with something reasonable, that looks a little off sometimes, and also never varies too far from the expected shape, like real puzzles do. A tangent on the "multiple solutions" thing - some large commercial puzzles are (evidently) larger than the maximum die size, so they are cut with multiple copies of the same pattern. A 5000-piece puzzle might have four copies in a 2x2 grid.