I don't think there is free/open source software out there. The only ones who need this kind of software are very big 3D printing companies and puzzle makers.
I have made an attempt at writing my own software a while ago, but the results were not good enough: viewtopic.php?f=7&t=21658
Now when you posted this topic I was actually working on a second attempt. It uses a more sophisticated approach by voxtelizing each object and approximating the shape with a convex hull. Using 0.5mm cubed voxtels gives quite reasonable results and I've gotten my first usable packing from it. Unfortunately the algorithm/my implementation (which really just enumerates the positions and just successively places the parts wherever they fit) is really slow (30 minutes per puzzle) and it does not always work. But I am quite happy at this first result:
d85d6993b3554a77b3a9443.png [ 116.84 KiB | Viewed 1173 times ]
But I figured out a method that would allow the software to place each part in a number of different orientations without taking a big performance hit. Once I implement this it may work much better.
But then, I am not sure if I can get it to work well enough. I think this model is "easy" because there are so many tiny parts. The algorithm places the largest parts first and then the smaller ones. Placing the large parts takes the most time and then the smallest ones can be inserted quite quickly so I'm kind of scared to apply this to a model with only large parts.