Jigsaw Puzzle algorithm?

Obviously a solution might not always be possible. It would depend on the pieces available as well as the dimensions of the rectangle. This seems like in general it would be an intractable problem (exponential time algorithm). This could explain why it is taking to long. Personally I can't see how you could improve your algorithm but perhaps there is some structure which you are not considering here. Is the total area of available blocks just slightly more than the area of the given rectangle. If so then you know most of the blocks must be used to make the rectangle. It may be faster to just exclude blocks from possible combinations and work from there. Also there may only be a few combination of blocks that have the same area as the given rectangle. Anything that narrows the number of possible solutions will speed up the algorithm.