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 |
---|---|---|

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) '
````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:

- 10
^{9}solutions with the “T” pieces. - 10
^{15}solutions with the “S” pieces.

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.