Eric Spencer
projects
A hobby project with no claim to usefulness. The puzzle it solves is this wooden puzzle on Amazon: 54 identical T-shaped blocks that pack into a 6×6×6 cube. Taking it apart is one thing and putting it back together is another, and the solver is the dignified alternative to trying again by hand.
A T-tetracube is four unit cubes arranged in a T. Fifty-four of them is exactly 216 unit cells, which is exactly a 6×6×6 cube, so the arithmetic lines up. The hard part is everything else.
The solver uses Knuth's Dancing Links, also called DLX, or Algorithm X. The packing question becomes a large binary matrix in which rows are "this piece in this position and orientation" and columns are "this cell of the cube must be covered exactly once". The search recursively picks rows that cover all the columns without overlap, using a doubly-linked list trick that removes and reinserts rows and columns in O(1).
For this puzzle the DLX matrix is 1440 rows by 216 columns. The T-tetracube has 12 distinct 3D orientations rather than the 24 the cube rotation group would suggest, because the T's own symmetry collapses half of them, and each orientation has on the order of a hundred legal anchor positions inside the cube. A valid solution is any 54 rows that cover every column exactly once.
The awkward part of any combinatorial puzzle like this is that a plain search counts the same arrangement 24 times, once for each rotation of the cube itself. So every solution found is rotated through the full 24-element cube rotation group, the lexicographically smallest version is kept as the canonical form, and later solutions are deduped against it. What is left is the count of genuinely distinct tilings, modulo rotational symmetry.
The solver produces something like 40 solutions per second before dedup. Full enumeration is hours to days and has never been run to completion, so the exact number of solutions is still unknown.
The other half of the project is a Three.js viewer that loads the precomputed solutions. It orbits around the cube, explodes the pieces apart, toggles wireframe, and steps through solutions one at a time.
Source is on GitHub: https://github.com/EricSpencer00/cubed-pack-solve.