Haven't made a game like this before. However in the free e book: level 0 for C2 it goes over a jigsaw game. In it it confines the pieces within a box and gives each piece random angles and shoots it as a bullet to mix them up.
My thoughts are that you could create the puzzle assembled and then randomly change the angles about 90 deg while making them all bullets. If done for a long enough time it could jumble up the puzzle, but only in a way that is repeatable to get back to where you started.