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:
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:
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 creativecrafthouse.com 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 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|
| “T” solutions | 1 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 4 | 4 |
| “S” solutions | 2 | 2 | 2 | 2 | 2 | 2 | 6 | 14 | 32 | 33 |
| Pieces to place | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| “T” solutions | 8 | 8 | 8 | 16 | 16 | 16 | 16 | 16 | 16 | 16 |
| “S” solutions | 107 | 369 | 379 | 379 | 758 | 1516 | 3032 | 3032 | 6064 | 6064 |
| Pieces to place | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
| “T” solutions | 16 | 32 | 32 | 64 | 64 | 64 | 360 | 646 | 1102 | 1102 |
| “S” solutions | 37082 | 54592 | 54592 | 93208 | 93208 | 672142 | 1189974 | 1189974 | 4289574 | 5291538 |
| Pieces to place | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 |
| “T” solutions | 1102 | 1102 | 8094 | 38694 | 59126 | 235693 | 235693 | 235693 | 235693 | 471386 |
| “S” solutions | 12179980 | 43909804 | 87819608 |
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 naive 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) 'sol.data' using 1:2 via a,b
fit t(x) 'sol.data' using 1:3 via c,d
plot 'sol.data' using 1:3 title "S solutions", \
s(x) title "S best fit", \
'sol.data' 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.
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.