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||“T” solutions||“S” solutions|
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) '
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|
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.