_____ _ ____
| ____|_ __(_) ___ / ___| _ __ ___ _ __ ___ ___ _ __
| _| | '__| |/ __| \___ \| '_ \ / _ \ '_ \ / __/ _ \ '__|
| |___| | | | (__ ___) | |_) | __/ | | | (_| __/ |
|_____|_| |_|\___| |____/| .__/ \___|_| |_|\___\___|_|
|_|
This is a hobby project with no business being useful. The puzzle it solves is this wooden puzzle on Amazon: 54 identical T-shaped blocks that supposedly pack into a 6×6×6 cube. Taking it apart is one thing, 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 at least lines up. The hard part is everything else.
The solver uses Knuth's Dancing Links, also called DLX, or Algorithm X. The short version: the packing question becomes a giant binary matrix where rows are "this piece in this position and orientation" and columns are "this cell of the cube must be covered exactly once." The search then 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 (you'd expect 24 from the cube rotation group, but the T's own symmetry collapses half of them), and each orientation has somewhere 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 annoying 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 that. What is left is the count of genuinely distinct tilings, modulo rotational symmetry.
The solver churns out 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 and lets you orbit around the cube, explode the pieces apart, toggle wireframe, and walk through solutions one at a time. You can try it here: ericspencer.us/cubed-pack-solve.
Source is on GitHub: https://github.com/EricSpencer00/cubed-pack-solve.