Many puzzle pieces have complex shapes with inevitable overhangs whichever way you orient them. I would like to try soluble support material but I don't yet have dual extruder printing capability. Ordinary support material leaves nasty marks on the downward-facing surfaces.

My latest idea was to split the piece horizontally through the middle and print the two halves facing upwards with a custom connecting joint on top of each piece. The joint consists of a triangular peg next to a triangular hole, all contained within the outline of a single cube.
The prototype was first modelled in Tinkercad and then transferred to OpenSCAD for easier customisation.
Watch the video of the first test at http://youtu.be/Fp63gR9HTJA

Update April 2019 - make sure you check out Aaron Siegel's fabulous Puzzlecad which takes this idea to the next level.