2
$\begingroup$

Input: set of bricks, each one is made of 1x1x1 cubes glued together face to face, like tetris pieces.

Problem: find the way of putting together those pieces to make a solid that contains biggest full cubical subsolid.

Is there any smart algorithm I could use in this kind of problem? The only solution that comes to mind is ordinary brute force. I'm looking for ideas for an accurate algorithm as well as an approximation algorithm.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Shouldn't we expect it to be NP hard to know whether they can be assembled to have a subsolid of a certain size? $\endgroup$
    – Joel David Hamkins
    Commented Oct 15, 2011 at 10:46
  • $\begingroup$ To add support for Joel's hunch, "Tetris is Hard, Even to Approximate": arxiv.org/abs/cs/0210020 . Their proofs use reductions from 3-partition. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 15, 2011 at 14:11
  • $\begingroup$ I edited to add the image, and cleaned up some grammar. I am not clear, however, on the intended meaning of "full", whether it means a cubical subsolid, or merely rectangular. $\endgroup$
    – Joel David Hamkins
    Commented Oct 15, 2011 at 19:01
  • 1
    $\begingroup$ @Joel: I read it as meaning (i) the subsolid should be a perfect cube, and not just a large rectangle, and (ii) the subsolid should be convex, rather than say having some empty interior. If this is not the correct reading, I hope @mn will revise the question. $\endgroup$
    – Theo Johnson-Freyd
    Commented Oct 16, 2011 at 1:05
  • $\begingroup$ @Theo Johnson-Freyd: that is exactly what I meant $\endgroup$
    – m n
    Commented Oct 16, 2011 at 14:01

2 Answers 2

Reset to default
2
$\begingroup$

In general the problem should be NP-hard. While this may not be a reduction, I am thinking of trying to pack n^2 many 1 by 1 by n bins with 1 by 1 by k bricks, where k actually means many bricks of different sizes; if I am right, bin packing can be reduced to your problem.

If the bricks are of few types, it may be possible to construct quickly tiling solutions that allow one to get nice approximations. For example, 3 of the 7 blocks used to build a Soma cube each tile the 2x2x2 cube, so given any count of those 3 kinds of blocks, you can likely come within O(1) of the maximal cubical volume achievable using little more than arithmetic; if you can generate dissections of small cubes or prisms with your input bricks, you can then quickly decide which of many rectangular prisms are nicely buildable with the given tile set, and this can be used to approximate the maximal rectangular volume, or maximal cubical volume, as desired. Note that this does not contradict the above (idea for a) reduction because k in this instance is bounded from above by some small number.

Gerhard "Ask Me About System Design" Paseman, 2011.10.15

Improve this answer
$\endgroup$
1
  • $\begingroup$ In the example using 3 kinds of blocks, it is easy to construct cubes of side length 2n with sufficient even quantities of the blocks, and figures which are "2n+1 cubes with three bumpy sides" given sufficient quantities of all the blocks, so this particular problem has most cases nicely solvable in linear or near linear time, depending on how long it takes to compute a cube root. Gerhard "Ask Me About System Design" Paseman, 2011.10.15 $\endgroup$
    – Gerhard Paseman
    Commented Oct 16, 2011 at 5:09
0
$\begingroup$

Look at dimension $n=2$. Then this reduces to finding a clique or independent set of given size $k$ which is NP-complete when the cubes (squares) are arbitrarily placed on $\mathbb{Z}^{2}$. Hence, this is NP-complete for higher dimensions in general case. It would be interesting to look at semidefinite relaxations of this problem (say call it as higher dimensional clique or independent set problem).

Having said that your problem is specific - in the sense - the cubes are not disjoint and the number of cubes in higher rows is lower than number of cubes in lower rows - for $n=3$, this specific case is most likely $O(N^{3})$ as it looks like scanning each row from bottom may suffice ($N$ is maximum of rows in all dimensions).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .