Step 1: Slice the image into a grid of whatever size you want, for example 36x28 for a 1000 piece puzzle. But make the grid lines wavy instead of straight. Use the sine function. The frequency along each axis should be n/2 if n is the number of pieces along this axis (perhaps this isn't necessary, need to try). Use slightly varying random amplitude for extra randomness for each grid line.
Step 2: For the little piece "connectors" use splines or something similar. Maybe a mix of splines and arcs. Each connector could be made of two Bézier splines with random control points within a range dictated by the grid lines:
- The first control point of the first spline would have to be on the side of the piece somewhere inside the first half (or second 6th or something).
- The last point of the second spline would also be on the side but in the 5th sixth.
- The last point of the first spline and the first point of the second spline have to be the same and should be some distance to the left or right (up or down) from the vertical (horizontal) side of the piece. Select the side depending on where the apex of the sinewave grid line is. The spline control point should be on the opposite side of the sine apex.
- The third point of the first spline must be on the "outside" of the line connecting p0 and p3 of the spline. The same goes for p1 of the second spline, it must be on the "outside" of line connecting p0 and p3 of the second spline. What "outside" means depends on when p3 of the first spline (and p0 of the second) is. Also points P2(1), P3(1), P0(2) and P1(2) must all lie on the same line.
- Points p1 of spline1 and p2 of spline2 must lie on the opposite side of p2 and p1 respectively.
When you connect all the control points with splines, you will get the familiar shapes you can see in most jigsaw puzzles. If you select slightly random values (within the bounds), no two pieces will be the same. You can also select how regular or odd looking you want the pieces to be. Narrow the bounds within which you select the spline control points and the pieces will be more regular, widen the bounds and the pieces will look odd.
Here's also a picture of what I mean: