So I was analyzing the Calibron 12 puzzle and to me it looks

So, I was analyzing the Calibron 12 puzzle and to me it looks like a bin-packing problem. Is this puzzle actually a bin-packing problem and thus NP-hard for the perfect solution?

Basically, you can make your own calibron 12-ish puzzle by doing the following:

Take a rectangular piece of wood. Cut the wood into randomly sized rectangles. Jumble the pieces. Now put it back together into the exact same shape. (note there are technically 4 solutions, due to mirroring vertically or horizontally also fitting the exact shape)

Solution

It depends what you mean by this puzzle. If you mean specifically Calibron 12 then no, there is no growth factor (there are only ever 12 pieces) so the solution can be found in constant time (a very slow constant).

If however you want to know about puzzles of this nature it is hard to determine. The problem could potentially be phrased as, Is there some arrangement of these n objects that can completely fill this square. Now to me this does not seem likely to be polynomial-time in nature (I am speculating based on the permutations of arrangements, but I do not have a proof).

The bin packing comparison does not really work however since this has almost nothing to do with separating n objects into the smallest number of bins. This is a category of questions called tiling problems.

Here is a paper that deals with Rectangle tiling, which is a related problem.