The Bedlam Cube

The Bedlam Cube is a $4 \times 4 \times 4$ polycube dissection. Thirteen pieces — twelve pentacubes and one tetracube, totalling $12 \cdot 5 + 4 = 64$ unit cubes — must be assembled into a solid cube of side four. The piece set was chosen so that no piece repeats (as with the related Soma Cube), and most of the pieces have little symmetry: of the thirteen, seven have the full twenty-four rotational orientations, five (including the lone tetracube) have twelve, and only the cross-shaped piece, with its fourfold symmetry, has as few as three. The resulting puzzle is far harder than its flat relatives: not because the pieces are subtle, but because the $4 \times 4 \times 4$ cell count is large, each piece has up to twenty-four rotational orientations, and the interactions between adjacent pieces propagate along three axes at once.

The cube has $19\,186$ distinct solutions, a count first published by Scott Kurowski. For any given tiling, the thirteen pieces can be identified by their canonical letter names (Little Corner, Spikey Zag, Pokey Corner Bit, Right Angles Everywhere, Middle Zig, Pokey Z, Corner Joist, Dented L, F in Therapy, Flat M, Cross, Confused F, T-Bone) and located in the cube by their occupied coordinates. None of the pieces is a repeat of another, so pairs of the form “which copy of piece $X$” do not arise; the twelve pentacubes are twelve of the twenty-nine distinct pentacubes, and the one tetracube is one of the eight distinct tetracubes.

Exact cover is again the natural formulation. The cube has $64$ cells, each piece must be placed exactly once, and every cell must be covered exactly once. What distinguishes this chapter from the two that preceded it is simply the move to three dimensions: the orientation group has $24$ elements rather than $8$, and placements are enumerated over translations in three axes rather than two.

The pieces

Each of the thirteen pieces is a connected polycube in the cubic lattice. The canonical coordinates, taken from Scott Kurowski’s enumeration, are:

Piece A is the one tetracube; B through M are the twelve pentacubes. Three of the pentacubes are planar (they fit into a single layer: pieces J, K, and L are planar; B, C, D, E, F, G, H, I, M all have cells at two different $z$-coordinates and so are genuinely three-dimensional).

The programming model

Orientation group

In three dimensions, the rotation group of the cube has $24$ elements. Given a piece’s canonical coordinate list, enumerate its distinct orientations by applying the group generators and de-duplicating; this collapses to fewer than $24$ orientations for pieces with rotational symmetry, but most Bedlam pieces produce the full count. Reflections are not included: the Bedlam Cube is the chiral puzzle, and adding mirror images would introduce extra “pieces” that do not exist in the physical set.

Placements

For each piece $P_i$ and each orientation $o$, enumerate every translation $(dx, dy, dz)$ such that all cells of the translated orientation lie inside the $4 \times 4 \times 4$ cube. Each surviving (piece, orientation, translation) is a placement.

Placement variables

For each placement $p$ of piece $P_i$, introduce a Boolean variable $x_p \in \{0, 1\}$ with $x_p = 1$ meaning “this placement is selected.”

Constraints

Each piece is placed exactly once: $$\sum_{p \,:\, \text{placement of } P_i} x_p \;=\; 1.$$

Each of the $64$ cells is covered exactly once: $$\sum_{p \,:\, (x, y, z) \in \text{cells}(p)} x_p \;=\; 1.$$

A solver in eighty lines

from ortools.sat.python import cp_model

PIECES = {
    "A": [(0,0,0),(0,0,1),(1,0,0),(1,1,0)],
    "B": [(0,0,1),(0,1,0),(0,1,1),(1,1,0),(1,2,0)],
    "C": [(0,0,0),(0,1,0),(1,1,0),(0,1,1),(0,2,0)],
    "D": [(0,0,0),(0,0,1),(0,1,0),(0,2,0),(1,2,0)],
    "E": [(0,0,0),(0,1,0),(0,1,1),(1,1,0),(1,2,0)],
    "F": [(0,0,0),(0,0,1),(0,1,0),(1,1,0),(1,2,0)],
    "G": [(0,0,0),(1,0,0),(0,0,1),(0,1,0),(0,2,0)],
    "H": [(0,0,0),(1,0,0),(1,0,1),(0,1,0),(0,2,0)],
    "I": [(0,0,0),(0,0,1),(0,1,0),(1,1,0),(0,2,0)],
    "J": [(0,1,0),(1,0,0),(2,0,0),(1,1,0),(0,2,0)],
    "K": [(0,1,0),(1,0,0),(1,1,0),(2,1,0),(1,2,0)],
    "L": [(0,0,0),(1,0,0),(1,1,0),(2,1,0),(1,2,0)],
    "M": [(0,1,0),(1,0,0),(0,1,1),(1,1,0),(1,2,0)],
}
N = 4

def norm(p):
    mx = min(x for x,_,_ in p)
    my = min(y for _,y,_ in p)
    mz = min(z for _,_,z in p)
    return tuple(sorted((x-mx, y-my, z-mz)
                        for x,y,z in p))

def rotX(p): return [(x,-z,y) for x,y,z in p]
def rotY(p): return [(z,y,-x) for x,y,z in p]
def rotZ(p): return [(-y,x,z) for x,y,z in p]

def orients(p):
    pool = {tuple(norm(p))}
    frontier = set(pool)
    while frontier:
        nxt = set()
        for q in frontier:
            for g in (rotX, rotY, rotZ):
                r = tuple(norm(g(list(q))))
                if r not in pool:
                    pool.add(r); nxt.add(r)
        frontier = nxt
    return [list(o) for o in pool]

def solve():
    m = cp_model.CpModel()
    pls = []
    for name, shape in PIECES.items():
        seen = set()
        for o in orients(shape):
            mx = max(x for x,_,_ in o)
            my = max(y for _,y,_ in o)
            mz = max(z for _,_,z in o)
            for dx in range(N - mx):
                for dy in range(N - my):
                    for dz in range(N - mz):
                        cells = frozenset(
                            (x+dx, y+dy, z+dz)
                            for x,y,z in o)
                        if cells in seen: continue
                        seen.add(cells)
                        pls.append((name, cells))
    v = [m.NewBoolVar("") for _ in pls]
    by = {}
    for i,(n,_) in enumerate(pls):
        by.setdefault(n, []).append(i)
    for n, idxs in by.items():
        m.Add(sum(v[i] for i in idxs) == 1)
    cov = {}
    for i,(_,cs) in enumerate(pls):
        for c in cs:
            cov.setdefault(c, []).append(i)
    for idxs in cov.values():
        m.Add(sum(v[i] for i in idxs) == 1)
    s = cp_model.CpSolver()
    s.Solve(m)
    return [pls[i] for i,x in enumerate(v)
            if s.Value(x)]

The enumeration produces about $4\,200$ placements; CP-SAT returns a single solution in just over one second.

Reading the solution

The solution is displayed three ways. Figure 4.1 shows four axonometric views of the whole cube, obtained by rotating the cube through $90^\circ$, $180^\circ$ and $270^\circ$ about its vertical axis: the four views together expose all six outer faces. Figure 4.2 shows each of the thirteen pieces individually in the same coordinate frame, with the outer $4 \times 4 \times 4$ cube rendered as a thin wireframe and only the focus piece drawn in full colour; this makes the spatial position of every piece explicit, including the pieces buried in the interior. Figure 4.3 gives the information-complete view: four $z$-slices from $z = 0$ (bottom) to $z = 3$ (top), each cell labelled by its piece letter.

Sources. The Bedlam Cube was invented by the British designer Bruce Bedlam, who developed it in the early $1980$s; it reached wide commercial release in $2004$. It is a larger, non-repeating cousin of Piet Hein’s Soma Cube ($1933$). The solution count $19\,186$, counting tilings up to the $24$-fold rotational symmetry of the outer cube, is due to Scott Kurowski, whose enumeration was the first complete census; because the piece set is chiral, reflecting a solved cube never produces another packing of the same thirteen pieces, so rotations alone generate the symmetry classes and the rotations-only census is the natural one. The solver of the preceding section recovers a single tiling by default. The CP model does not break the outer cube’s rotational symmetry, so setting $\texttt{parameters.enumerate\_all\_solutions} = \mathtt{True}$ and iterating over feasible models enumerates $24 \times 19\,186 = 460\,464$ tilings; dividing by the $24$ rotations of the assembled cube recovers Kurowski’s count of $19\,186$. Chlond presents the same polycube-packing integer program, with the Bedlam Cube as its principal worked instance, in the INFORMS Transactions on Education Puzzles column (“Box-Packing Puzzles,” 5(3): 70–72, 2005).