Introduction

I was recently playing with the Soma cube, a puzzle comprising a set of seven polycubes that can be assembled into a 3x3x3 cube, as shown below.

The Soma cube is one of the more widely known such “packing puzzles,” and although I’m not very good at solving puzzles like this– my wife is much better at this than I am– I didn’t find it terribly difficult to put together. This is maybe not very surprising: there are 11,520 possible oriented solutions, 480 distinct up to rotation of the cube. Which raised the question: how much harder can we make this puzzle? More precisely, among all puzzles of distinct polycubes to be packed into a 3x3x3 cube, is there a “hardest” such puzzle in some quantifiable sense, that agrees with our subjective human perception of difficulty?

Making polycubes

The first step toward answering this question was to make polycube puzzle pieces. Each polycube is a 3D-printed STL model, created using OpenSCAD and the PuzzleCAD library, that together made it very easy to generate nice models, including insetting faces and beveling edges of the cubies, so that puzzle pieces fit together easily but snugly. The following example script shows the PuzzleCAD parameters that I used (units are millimeters, so that a solved 3x3x3 cube is about 2 inches on each side), with the last line specifying the particular polycube to generate, in this example the tetracube 4-007 (shown above in magenta):

include <puzzlecad.scad>
$burr_scale = 17;
$burr_inset = 0.3;
$burr_bevel = 1.3;
$unit_beveled = true;
burr_piece(["xx|.x", "x.|.."]);

To generate the corresponding STL model file 4-007.stl in binary format, from the OpenSCAD input script file polycube.scad above:

openscad --export-format binstl -o 4-007.stl polycube.scad

All of the source code is available on GitHub, along with STL model files for all 207 polycubes up to hexacubes.

Measuring puzzle difficulty

We can enumerate all possible puzzles involving hexacubes or smaller as solutions to an exact cover problem, considering all possible positions and orientations of each polycube, searching for subsets of such oriented polycubes that exactly “cover” a 3x3x3 cube. However, each puzzle, defined as a subset of distinct unoriented polycubes (think of buying the puzzle pieces jumbled haphazardly in a bag), will generally appear some number times in this list of exact cover solutions, once for each way of positioning and orienting all of its particular polycubes. For example, even those puzzles with a unique solution will appear times, once for each possible rotation of the solved cube. The Soma cube appears times, with 24 “copies” of the 480 solutions that we would typically consider truly distinct, differing by more than just a rotation of the solved cube.

Intuitively, the larger the value of — the larger the number of oriented solutions– for a given puzzle, the “easier” it should be to solve. For example, the figure below shows one of the two puzzles maximizing , with 3,030,672/24=126,278 distinct solutions up to rotation. (The other “easiest” puzzle is essentially a “mirrored” version of this one, with polycube 4-007 replaced by its chiral counterpart 4-008.)

So far, this tracks pretty well with manual experiment: no matter how you jumble these eight polycubes to start, they seem to almost “fall together” snowball-style into a solved 3x3x3 cube.

However, if we want the hardest puzzle, we want smaller values of , i.e., fewer solutions. But this metric alone still needs further refinement, since it turns out that, among all 19,276,753 possible puzzles involving hexacubes or smaller, 5,633,564 of them have unique solutions. That is, nearly 30% of all puzzles have the same minimum value . Surely some of these uniquely solvable puzzles are harder than others?

To handle this, I tried what seemed like the simplest thing that could possibly work: for each puzzle, define the difficulty “score” to be the ratio , where the numerator is the “breadth” of the brute force search tree. More precisely, counts how many ways we can (1) pick a first polycube, then (2) place and orient it somewhere in the yet-to-be-solved 3x3x3 cube. Put another way, is the number of rows in the matrix form of the “reduced” exact cover problem for that puzzle.

Intuitively, the larger the value of , the “wider” the search tree, and thus the harder it is to begin, so to speak, resulting in a larger difficulty score . Similarly, the smaller the value of , the fewer the number of possible solved configurations, also resulting in a larger difficulty score.

Results

The following histogram shows the resulting distribution of difficulty of all 19,276,753 possible puzzles involving hexacubes or smaller. Note that both axes are on a logarithmic scale; for example, the light and dark blue comprises the 387,347 puzzles without hexacubes, which make up only about 2% of the total.

The two mirror-image easy puzzles described earlier live at the far left of this figure. At the far right of the figure, the two hardest puzzles, both with unique solutions, are also a chiral pair, one of which is shown below. (The other replaces polycube 6-057 with its mirror 6-095.)

If we restrict our space of possible puzzles to pentacubes or smaller (shown in blue in the histogram above), then the hardest puzzle– again one of a chiral pair (the other replaces 5-024 with 5-027)– is shown below.

My wife was a helpful willing subject in these experiments. As mentioned, the easy puzzle was not even a puzzle, fitting together in seconds. The Soma cube was also straightforward, solved within minutes. To my delight, the two hardest puzzles above really were hard: it took a couple of hours to solve the pentacube version.

Interestingly, the hexacube version– with the slightly greater difficulty score– took less time, only about an hour. She did solve that one after the pentacube version, though; maybe we “warm up” our minds into puzzle-solving mode?

One way in which this difficulty metric seems flawed is that polycubes can contribute to a large tree breadth in two different ways: the single cubie, for example, can be positioned in 27 different locations in the 3x3x3 cube, despite lacking any distinct rotations; at the other extreme, even large polycubes, like most of the hexacubes, can be rotated into 24 different orientations, even if they don’t have much translational wiggle room. It’s not clear to me whether these two extremes should have similar contributions to difficulty score. (The polycube 5-026 above is an interesting middle ground, in that it’s asymmetric enough to have many orientations, but small enough to have many translations as well, so that it has the maximum overall contribution to tree breadth, with 192 possible oriented positions in the solved cube.)