Following the steps to create the pattern renders a fairly realistic puzzle shape, and it should take only a few minutes to do. Save the pattern as a path, so you can use it again if you need to. Another advantage of paths is that they are infinitely scalable: You can apply your puzzle path to any size image.
Creating a path allows you to easily create the puzzle shape; all that has to be created is a single path. Duplicating the path and flipping/rotating it creates some variance. Once the whole path pattern is created, there are a number of ways to apply it to any image.