# biggest cube problem (given set of bricks)

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.

-
Shouldn't we expect it to be NP hard to know whether they can be assembled to have a subsolid of a certain size? – Joel David Hamkins Oct 15 '11 at 10:46
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. – Joseph O'Rourke Oct 15 '11 at 14:11
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. – Joel David Hamkins Oct 15 '11 at 19:01
@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. – Theo Johnson-Freyd Oct 16 '11 at 1:05
@Theo Johnson-Freyd: that is exactly what I meant – m n Oct 16 '11 at 14:01

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.

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).