Model originally uploaded to Thingiverse at https://www.thingiverse.com/thing:27695.
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.