1
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ Can you formalize the rules of this game and try to explain your intuition? Now it reads like an advertisement ... $\endgroup$ – Pål GD Jun 20 '14 at 17:48
  • 1
    $\begingroup$ "4 solutions" $\: \mapsto \:$ "at least 4 solutions" $\;\;\;\;$ $\endgroup$ – user12859 Jun 20 '14 at 18:06
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I like the first part of your answer. But the part where you say: "this is definitely not polynomial" - How do you know? Do you have a proof of NP-completeness for some asymptotic version of this problem? If so, what is the NP-complete language, and what is the proof? Or are you just guessing that probably some asymptotic version of this problem will be NP-complete? If so, it would be better to label it as guessing/speculation. $\endgroup$ – D.W. Jun 20 '14 at 19:51
  • $\begingroup$ A good point, i'll edit that $\endgroup$ – lPlant Jun 20 '14 at 19:59
2
$\begingroup$

In order to answer this question you need to generalize the puzzle. The following generalized version of the puzzle is NP-complete:

Packing puzzle

Given a set of $n$ rectangles given by their widths and heights $(w_1,h_2),\ldots,(w_n,h_n)$ is it possible to pack them in to a $W\times H$ rectangle?

Membership in NP is trivial. One possible reduction to show completeness is from 2-Partition, which asks if it is possible to divide a set of numbers $x_1,\ldots,x_n$ with sum $2M$ in to two sets so that both sets sum to $M$.

The reduction is obtained by setting $W=M$ and $H=4M$, and for every number $x_i$ making an input rectangle $(x_i,2M)$. Any solution of the puzzle is then also a solution to the partition problem, since the pieces only fit in to the rectangle in a vertical orientation. A solution will consist of two horizontal rows of pieces, and the pieces that are in each row correspond to the partition.

$\endgroup$
  • $\begingroup$ What is the argument for membership in NP? $\;$ $\endgroup$ – user12859 Jun 25 '14 at 8:52
  • $\begingroup$ @RickyDemer The certificate is just the co-ordinates and orientation of all the pieces. It seems easy to verify that all the pieces are used and that they're all within the target rectangle with no overlaps. Am I missing something? $\endgroup$ – David Richerby Jun 25 '14 at 9:31
  • $\begingroup$ @DavidRicherby : $\;\;\;$ I don't see how one could verify that. $\:$ Consider, for example, numbers 11 and 17 on this page. $\;\;\;\;\;\;\;$ $\endgroup$ – user12859 Jun 25 '14 at 9:36
  • $\begingroup$ @RickyDemer The mechanics of the puzzle require the edges of all bricks to be axis-parallel in any solution. We're trying to arrange the bricks to reconstruct the rectangle they were originally cut from, not see how many of the bricks we can fit into some other space. $\endgroup$ – David Richerby Jun 25 '14 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.