Geometry : Polycubes (and Polyominoes)

TL;DR
POLYCUBES Viewer
POLYOMINOES Viewer

Introduction

Everything started with this YouTube video from Computerphile : Mike's Cube Code where Mike Pound introduces the concept and shares his attempt at enumerating the polycubes with their number of cubes n with some basic Python code. I suggest you watch the video but if you don't, polycubes are shapes formed by the connection of cubes face to face. All cubes have the same size (let's say their side length is 1). Any cube may have up to 6 neighbors in the six possible directions: up, down, left, right, front, back. In any polycube, also called a lattice animal, there is no cube or set of cubes that is separated from the rest.

Since some mathematicians seem to like counting, they have tried counting the number of different polycubes that can be made from n cubes. For precise enumeration, one would need to not overcount or undercount and so define whether two shapes are the same or not. The rules are that two polycubes that differ by reflection are considered different and that two polycubes that differ by rotation are considered identical (there are 24 possible rotations for a given polycube). The result from this computation is available on the Online Encyclopedia of Integer Sequences (OIES) as sequence A000162 up till n=14 and on Kevin Gong's website up till n=16. As you can see, the growth is exponential with a growing factor of around 7. The main algorithm for this computation is to generate polycubes of level n by adding a cube at every possible position on every polycube of level n-1 and discard the identical ones. This growing procedure guarantees that the shapes are always connected and that none is by-passed but the computing time and memory consumption are huge.

The last computation (n=16) is from 2004. Thanks to the Computerphile video, a collaborative open-access Github repository was created: Opencubes where people have started improving the original code, implementing it with other languages and discussing computation techniques. So if you feel like you could make some progress on the matter, I invite you to participate !

I was not satisfy with the rendering tool from the repository. It would generate a view over all the polycubes dispatched over a big plane. So, I decided to make my own viewer. The requirements were to load big datasets, with potentially billions of polycubes, big or small, browse through the models rapidly and rotate around each model. For big model, the limit is the GPU instancing of your computer but ten or hundred thousand cubes on a single polycube is okay. For datasets, I have managed to compress the data and load it into memory in an optimized way. Though, my server drive being only a few gigabytes large, I won't upload larger datasets. You can still view your own datasets if they are in the correct format.

Polycubes that fits exactly into a 3x3x3 cuboid

Actually, my first interest was related to modular origami. I had started building polycubes and planning for others using online voxel builders and suddendly became interested on the polycubes that could fit exactly into a 3x3x3 cube by spanning across this cube. What I mean is there should be at least a cube on each face of the 3x3x3 cube. This way, the shape would not fit into a smaller cuboid. With this restriction, it means that the smallest polycube is of length n=7 and the largest polycube is the 3x3x3 cube itself with n=27. Moreover, all polycubes with n>18 necessarily satisfy the requirement.

For the first step, I took the Python code from the Opencubes repo, modified and optimized it to generate all polycubes that would be contained in a 3x3x3 grid. The modifications are very light. For the first layer (n=1), every position in the 3x3x3 cube is considered as a starting position. The working volume is fixed, it is that of the 3x3x3 grid, which simplifies a lot the rotations (which can be precomputed as a set of permutations) as well as the comparison process because the keys that represent each shape are the same length (27). In the end, the speedup is by a factor of 4 or so for a total of around 20 minutes. All the shapes (1,597,143) are stored in a Numpy array.

For the second step, I just remove the polycubes that do not span across the 3x3x3 grid (it took a minute to run on my computer and removed 22,890 invalid polycubes). In the end, I have counted 1,574,253 polycubes over the 2^(3x3x3)=134,217,728 combinations in a 3x3x3 grid so a little bit more than 1%. The results are summed up in this table:

Polycubes in cuboids

Edit from 09/09/2023:

Before explaining why I have considered the computation of cuboids, I may explain how a polycube is encoded in the original code. In python, it is represented as a uint8 array with the minimum dimensions to hold it. Values in the array can be either 1 to indicate the presence of a cube or 0 for its absence. At some point, this array needs to be hashed so a hashable key is needed. This key is made of the grid dimensions which are coded onto a byte each then concatenated together with the flattened polycube array. The flattened array is packed in chunks of eight elements per byte and zero padded. This makes for a very simple packing scheme: x y z bits. This is also the encoding I use for the datasets files that I load into the viewer. Such a file can be compressed efficiently with gzip too.

When thinking about the computation of the polycubes of length n. I realized that they can be split into groups based on the minimum cuboid size that they can fit in. So instead of computing the big dataset, we could compute many smaller datasets, one for each cuboid large enough to contain a polycube of a certain length. Really that's all, since that from a cuboid shape we can compute easily the range of polycube lengths it can contain, we know which cuboids to compute.

Thanks to some very fast C code (from here ), I was able to compute the number of polycubes that fits into many cuboids. Please go see the table in the Annex if you want the numbers. I have yet to compute all the cuboids needed for n>10 though. I may update this table in the future if I spend some of my computer time on it.

Looking at the evolution of the number of polycubes with each count in a given cuboid, in a log scale, it certainly follows a polynomial equation of degree 2. I have no idea why though. I mean, I expect it to go up and down but not with this specific shape. Is there a formula that relates the shape of the cuboid to the coefficient of the polynomial ? I don't know.

After thoughts

Polycubes make for interesting puzzle games, the most well known is the Soma cube where a 3x3x3 cube has to be assembled from a set of polycubes, many variations exist for the polycubes that are part of the set. This could be a question on its own: let's say there are a certain number of polycubes in a set, what are all the numbers and shapes these polycubes could have and be assembled into the 3x3x3 cube.

I have seen other puzzles where a given shape had to be made with pentacubes only. I mean at this point, the realm of ideas becomes limitless.

As a final touch to this article, let me show you some of the polycubes I have made with modular origami and a lot of patience. From left to right: a T-Rex, a tree and an abstract four-legged shape, the central column is not into contact with the table beneath.

Annex