1. Introduction

A box-packing puzzle, or "polycube" puzzle, consists of a number of polycubes (assemblies of unit cubes) that are to be packed into a cubical box. Typically, the total number of unit cubes used to form all the polycubes of a particular puzzle is equal to the volume of the box to be packed. These types of puzzle have been around for at least 50 years and excellent insightful discussions can be found in Gardner (1961), Golomb (1994) and Berlekamp (1982) et al.

2. Two Easy Pieces

A very basic example taken from is to pack three unit cubes and six 2x2x1 pieces into a 3x3x3 box.

This is solved by a simple insight. The cross-sectional area of the box across each of three axes is 9 units whereas the larger pieces have an even numbered cross-sectional area across each axis. Hence, we cannot fill in a slice through any axis using only these pieces. This leads us to the conclusion that the unit cubes must be placed in the long diagonal of the box. Once this is realised then the remainder of the pieces fit around these cubes in an obvious way.

A little more difficult but still solvable by inspection is to pack the following into a 3x3x3 box. This is from the same website as the above.

3. The Soma Cube

The Soma Cube was invented by Danish puzzlist Piet Hein (Gardner, 1961). The story goes that he became distracted in a lecture on quantum physics by Werner Heisenberg and began to speculate as to how many irregular polycubes can be constructed from four or less unit cubes. He came up with the following complete list and also noticed that these may be packed into a 3x3x3 box.

4. The Bedlam Cube

The Bedlam Cube is a deceptively simple looking puzzle consisting of a set of 13 polycubes, as pictured, that must be packed into a 4x4x4 box.

The image is reprinted with permission from 3d Puzzles , a fine puzzle site and well worth a visit.

This variation was devised by Bruce Bedlam in 1987 and has been re-released in the spring of this year (Bedlam website,). The Bedlam Cube is orders of magnitude more difficult than the Soma Cube and it seems that with such packing puzzles the level of difficulty increases rapidly as the box size increases in relation to the piece sizes.

5. Formulation

We will now work towards a general IP formulation of polycube puzzles using the Bedlam Cube as an instance. It is useful to visualize 13 sets of virtual boxes labeled A to M. Each box in set A, for example, contains piece A at a particular location and orientation and set A contains a complete list. The decision variables are now, quite simply, for each box in each set, should it be included in a solution.

In order to identify and enumerate the various positions and orientations that each piece may adopt inside the 4x4x4 box we imagine each piece enclosed within its smallest possible rectangular box. Pieces A, B and C fit snugly into a 1x3x3 box, pieces D through L fit into a 2x2x3 box and piece M fits into a 2x2x2 box. For each of these box sizes we count the positions it may assume within the larger box and note that for each position there are 24 orientations. We will refer to a particular position and orientation of a piece as a "configuration". The results are summarized in the following table.

The constraints are such that one box only must be selected from each set and each cubelet of the 4x4x4 box must be occupied by one piece only.

This may be expressed more formally as follows.

p = 13

m_k - number of configurations of piece k

n = 64 - number of cubelets to fill

x_i,k = 1 if configuration i of piece k used, 0 otherwise

d_i,j,k = 1 if cell j is occupied when piece k is in configuration i , 0 otherwise

One piece only used from each set.

Each cubelet occupied by one piece only.

Viewed in this way the puzzle seems quite trivial but nevertheless it remains interesting in a couple of ways. Firstly, due to the large number of variables, obtaining a solution is computationally intensive and solution times grow at an alarming rate as the box size increases. It may therefore be of interest to those people concerned with computational complexity and algorithmic design. Secondly, despite the simple formulation, the pre-processing required to generate the sets of virtual boxes and post-processing to convert the IP output into a readable solution are quite challenging programming exercises.

6. An implementation in R and Lpsolve

Each piece is described by a three dimensional array of the appropriate dimensions containing ones and zeros. For example, piece L is:

A single piece in a particular orientation is represented by a 4x4x4 array containing ones and zeros as required. Given that the leftmost grid corresponds to the top layer, the following is a representation of piece L at the front, top right of the box.

0	0	0	0		0	0	0	0		0	0	0	0		0	0	0	0
0	0	0	1		0	0	0	0		0	0	0	0		0	0	0	0
0	0	0	1		0	0	0	1		0	0	0	0		0	0	0	0
0	0	1	1		0	0	0	0		0	0	0	0		0	0	0	0

The R functions piece.pos.r and all.orient.r will accept a list of arrays of piece descriptions and output an exhaustive list of arrays of virtual boxes as described above. The command file cube.solver.r calls these functions, builds constraint matrices, calls Lpsolve and finally, formats the solution output.

A copy of the R language and an interface to Lpsolve may be downloaded from the URL provided in the References section below. Once these are successfully installed unzip the file polycubes.zip into a directory, invoke R and change directory as appropriate. The solver may be invoked at the command line prompt as follows:

source("cube.solver.r")

When the command line prompt reappears a solution has been identified and may be displayed by issuing the command:

cube.sol

The solution found by the above is as follows. Again, the leftmost grid represents the top layer.

12	4	4	5		4	4	5	5		6	11	11	5		6	11	9	9
12	12	4	8		6	1	1	5		6	6	1	1		11	11	1	9
12	13	2	8		12	2	2	2		10	7	2	9		10	10	10	9
13	13	8	8		13	3	3	8		10	7	3	3		7	7	7	3

Included in polycubes are piece descriptions for the Soma Cube, the Bedlam Cube and Steinhaus's Dissected Cube and cube.solver.r may be easily amended to produce solutions for each.

References

Berlekamp, R.B., Conway, J.H, Guy, R.K. (1982), Winning Ways for your mathematical plays, Volume 2: Games in particular, Academic Press. ISBN 01-12-091102-7.

Gardner, M (1961), More Mathematical Puzzles and Diversions .

Golomb, S.W. (1994), Polyominoes:Puzzles, Patterns, Problems and Packings , Second Edition. Princeton University Press. ISBN 0-691-02444-8.

R Development Core Team (2004), R: A language and environment for statistical computing, R Foundation for Statistical Computing, Vienna, Austria. ISBN 3-900051-07-0,