Packing the “S” tetracube


In my previous article on packing tetracubes, I finished by noting that the problem of packing 54 “S” tetracubes into a 6×6×6 cube looked as though it was going to be pretty challenging.

And so it proved. In particular, I couldn’t find any way to break up the puzzle into sections that I could solve by hand. For a while I had the idea that you could start with a packing of the 4×4×2 cuboid:

And then use this technique to expand the packing from 4×4×2 to 6×4×2:

I tried for a long time to repeat the expansion to get a 6×6×2 slab, as I did for the “T” tetracube, but with no luck. Every attempt came to nothing, with this ring-shaped structure being a typical result:

1. A solution

In the end I gave up and wrote a computer solver (using Donald Knuth’s “Dancing Links” technique, of course), from which I learned that there is no way to pack 18 “S” tetracubes into a 6×6×2 slab. Here’s a 6×6×6 solution, courtesy of the computer:

2. Estimating the number of solutions

In my previous article, I linked to Keiichiro Ishino’s solutions for the “T” tetracube problem. Ishino also gives 11 solutions for the “S” tetracube problem. (Ishino’s puzzle website is well worth a browse. He gives solutions, and in many cases solution counts, for hundreds of polycube packing problems and interlocking burr puzzles. There’s a staggering amount of work on display here.) For both of these 6×6×6 packing puzzles, Ishino claims only that there are “20,000+ solutions”; presumably he stopped his computer search at that point.

An aside: at Dave Janelle sells versions of these puzzles called “Monster T” and “Monster Z”. The blurb for the former reads, “The 54 ‘T’ shaped pieces will make a 6×6×6 cube 20,000 different ways […] I found the design for these Monster Puzzles from a mathematician’s website and thought they would make fantastic puzzles.” I guess the anonymous “mathematician” must be Keiichiro Ishino.

There are of course many more than 20,000 solutions to these packing problems. In a few minutes my computer finds hundreds of thousands of solutions for both problems. So how many solutions are there altogether? Well, one very rough-and-ready way to estimate the number of solutions is to see how the number of solutions grows as a function of the number of pieces to be placed. If I instrument the solver so that each time it backtracks it reports the number of solutions found so far, then this is what I get:

Pieces to place “T” solutions “S” solutions
2 1 2
3 2 2
4 2 2
5 2 2
6 2 2
7 4 2
8 4 6
9 4 14
10 4 32
11 4 33
12 8 107
13 8 369
14 8 379
15 16 379
16 16 758
17 16 1516
18 16 3032
19 16 3032
20 16 6064
21 16 6064
22 16 37082
23 32 54592
24 32 54592
25 64 93208
26 64 93208
27 64 672142
28 360 1189974
29 646 1189974
30 1102 4289574
31 1102 5291538
32 1102 12179980
33 1102 43909804
34 8094 87819608
35 38694  
36 59126  
37 235693  
38 235693  
39 235693  
40 235693  
41 471386  

Notice that contrary to my hand-solving experience, it looks as though there are a lot more ways of packing the “S” tetracube than the “T” tetracube. But this is a single run of the solver, and it might just be the case that it has lucked into regions of the search space with more “S” solutions than average and/or fewer “T” solutions than average.

In order to extrapolate from this data, I need a model that I can fit it to. Here’s a very naïve model: the \(n\) pieces are distributed roughly evenly within the region to fill, with each piece taking one of \(m\) orientations, and there is then a probability \(p\) that a piece doesn’t overlap with any of its neighbours. If no piece overlaps with any neighbours, then there’s a solution. In this model the number of solutions is about \((mp)^n\). So let’s use Gnuplot to fit exponential curves to the data:

set key left
set logscale y
set yrange [1:]
set xlabel "Pieces"
set ylabel "Solutions"
s(x) = b * a ** x
t(x) = d * c ** x
fit s(x) '' using 1:2 via a,b
fit t(x) '' using 1:3 via c,d
plot '' using 1:3 title "S solutions", \
     s(x) title "S best fit",                  \
     '' using 1:2 title "T solutions", \
     t(x) title "T best fit"

Eyeballing the graph, I’m not altogether convinced by the goodness of fit for the “S” tetracube, but in the absence of a principled change to my model, fiddling with the curve equation is not going to improve matters. Here are the best-fit parameters that Gnuplot finds:

Final set of parameters Asymptotic Standard Error
a 1.76546 ± 0.08082 (4.578%)
b 3.47972×10−5 ± 6.62×10−5 (190.3%)
c 2.28617 ± 0.06749 (2.952%)
d 5.48797×10−5 ± 5.561×10−5 (101.3%)

And extrapolating to the puzzle with 54 pieces yet to place, there are about:

This suggests that with about a week of computer time I could get an exact count of “T” solutions, but counting the “S” solutions is well beyond my resources.

3. Improving the estimate

As I noted above, the solution counts generated from a single run of the solver might be unrepresentative. It would be better to get a more representative sample of the solution space. Something for another post, perhaps.