Twelve Pieces, Fifty-Five Holes: The Mathematics of an IQ Fit Puzzle

1. The puzzle, the pieces, and the rules

The variant this essay solves is a flat packing puzzle. The board is a rectangle of 11 columns by 5 rows — fifty-five holes. The pieces are twelve rigid clusters of joined balls. A move places one piece flat on the board so each of its balls sits in a hole. A solution places all twelve pieces so every hole is covered exactly once: no overlaps, no overhangs, no piece left unused.

That is the whole game. The rest of the essay is about counting the placements, proving that "full" means "solved," casting the search as an exact cover problem, and then encoding the board as a 64-bit integer so the solver can run on bit arithmetic.

The twelve pieces, read off a photograph of a physical set, are polyominoes drawn with balls instead of squares. Here is the inventory — one row per piece, with a short label, the conventional polyomino name, the ball count, and one orientation (# = ball, . = empty):

label  name               balls  shape

G      U pentomino           5   ooo
                                 o o

T      T tetromino           4    o
                                  oo
                                  o

Y      Y pentomino           5   oooo
                                   o

O      F pentomino           5    o
                                  ooo
                                   o

Pu     W pentomino           5    oo
                                   oo
                                    o

R1     L pentomino           5   oo
                                  o
                                  o
                                  o

R2     S tetromino           4     oo
                                  oo

Db     L tetromino           4   oo
                                  o
                                  o

Mb     V pentomino           5   o
                                 o
                                 ooo

Lb     corner triomino       3   o
                                 oo

Mi     P pentomino           5   oo
                                 ooo

K      N pentomino           5   oo
                                  ooo

Eight of these are pentominoes (five balls), three are tetrominoes (four balls), and one is a triomino (three balls). That gives 8 \times 5 + 3 \times 4 + 1 \times 3 = 40 + 12 + 3 = 55. Hold that number. It is the quiet engine of everything that follows.

A small curiosity for the connoisseur. There are exactly twelve free pentominoes in the classical set, traditionally named F, I, L, N, P, T, U, V, W, X, Y, Z. This box contains eight of them in their five-ball form (U, Y, F, W, L, V, P, N), but the T and the Z appear shrunk down to tetrominoes, and the I and the X are absent entirely, their place taken by a tiny corner triomino. So this is not "the twelve pentominoes in a trenchcoat." It is a cousin.

2. A mathematical analysis

Polyominoes, and what "the same shape" means

A polyomino is a connected set of unit squares joined edge to edge. Our pieces are the same objects drawn with balls. The subtle question is when two placements count as "the same shape."

Pick up a physical piece. You can slide it (translate), turn it in the plane (rotate by 90°, 180°, or 270°), and flip it over like a pancake (reflect). Translations move the piece around the board but do not change which orientation it is in. The orientations themselves come from the eight rigid motions that take a square to itself: four rotations, and for each rotation a mirrored copy. That set of eight motions is the dihedral group D_4 — think of it as the complete menu of ways you can pick up a square coaster and put it back into a square hole so the edges still line up.

Two placements that differ only by an element of D_4 are congruent. A shape counted up to all of D_4 is a free polyomino, which is the right notion for a physical puzzle: you really can rotate and flip each piece in your hand. So when we ask "how many distinct ways can this piece lie on the board," we are asking for the size of its orbit under D_4 — the set of distinct looks you get by applying those eight motions.

Here is the intuition for counting that orbit without listing every motion by hand. Some pieces look different under every motion — the F pentomino is the classic example. Others have leftover symmetry, like the U pentomino, which looks identical after a left-right flip; that flip is a do-nothing as far as the shape is concerned. Motions that leave a shape looking unchanged form its stabilizer. The more symmetry a piece has, the larger the stabilizer, and the fewer distinct orientations you get — because some of the eight motions are secretly the same look wearing a different label.

The orbit-stabilizer theorem turns that observation into arithmetic:

|\text{orbit}| = \frac{|D_4|}{|\text{stabilizer}|} = \frac{8}{|\text{stabilizer}|}.

A highly asymmetric piece has a trivial stabilizer of order 1, so it has 8/1 = 8 orientations. A piece with one mirror symmetry has a stabilizer of order 2, so it has 8/2 = 4. A piece with half-turn symmetry and nothing else likewise has 4. You never have to enumerate the full group once you can see the symmetries of the shape.

Applied to our box:

• The U pentomino, the T tetromino, the V pentomino, and the corner triomino each have a single mirror symmetry, so each has 4 orientations.
• The S tetromino (our R2) has a half-turn symmetry but no mirror symmetry, so it too has 4.
• The asymmetric ones — F, Y, W, the L pentomino, the L tetromino, P, and N — have no symmetry at all, so each has the full 8.

That is 4+4+8+8+8+8+4+8+4+4+8+8 = 76 distinct orientations across the whole box. Multiply each by the number of board positions where it fits, and you get the complete menu of candidate placements: a few hundred rows in the matrix we are about to build. The point is not the exact count. The point is that symmetry has already cut the search space by roughly half before we place a single piece, and it did so for free, by group theory.

The counting invariant: why "full" means "solved"

Now the number 55 earns its keep. Because pieces never overlap and never hang over the edge, the number of covered holes at any moment equals the sum of the sizes of the pieces placed so far. Suppose the board is completely full but, contrary to hope, we have not used all twelve pieces. Then the placed pieces sum to 55, while all twelve pieces also sum to 55, so the pieces left unused must sum to 55 - 55 = 0. But every piece has at least three balls, so a nonempty leftover set cannot sum to zero. Contradiction. Therefore the leftover set is empty, and a full board has used every piece.

The arithmetic above is exactly what the figure walks through: two sums forced equal, and a leftover that cannot be both nonempty and zero.

The converse is immediate: if all twelve pieces are placed without overlap, they cover 55 holes, which is the whole board. So "the board is full," "every hole is covered," and "all twelve pieces are used" are three ways of saying the same thing. This equivalence is not a nicety. It is the invariant that lets a solver stop the instant the board fills, with absolute confidence that no hole was skipped.

Exact cover: the puzzle as a matrix

There is a clean formalization that turns the whole puzzle into linear algebra over the booleans. Build a 0-1 matrix as follows. The columns come in two kinds. There is one column for each of the twelve pieces, recording the constraint "this piece is used exactly once." There is one column for each of the 55 holes, recording "this hole is covered exactly once." So there are 67 columns. The rows are the candidate placements: a few hundred of them, one for each (piece, orientation, position) triple. A row has a 1 in its piece's column and a 1 in each hole it covers, and 0 everywhere else.

The geometry's only job is to generate that set of candidate rows; nothing about shapes or positions survives past this point.

A solution is then a selection of rows such that every column contains exactly one 1 among the selected rows. The piece columns being covered once means each piece is used once; the hole columns being covered once means no overlap and no gap. This is the textbook definition of an exact cover problem. Donald Knuth's Algorithm X, ideally implemented with his dancing links technique, solves exactly this kind of matrix by recursive backtracking with a devastatingly effective heuristic: always branch on the column that currently has the fewest available rows, because that is where the puzzle is most constrained.

This reframing is worth pausing over, because it reveals what kind of object the puzzle really is. It is not a spatial puzzle that happens to admit a matrix description. It is an exact cover problem that happens to be drawn in plastic. The geometry is a convenient way to generate the rows; the solving is pure combinatorics.

A second invariant, for fun: coloring

Exact cover is the sledgehammer, but there are more delicate tools, and they are where the recreational mathematics gets charming. The classic one is a coloring argument. Color the 55 holes like a chessboard, alternating black and white. Because 55 is odd, the two colors cannot be equally numerous. A direct count gives 28 of one color and 27 of the other, an imbalance of one.

Now look at any single piece. Once placed, it covers some number of black holes and some number of white holes; sliding it by one square swaps the two colors, so the signed imbalance flips even though the absolute imbalance — how unevenly the piece splits the two colors — stays fixed by the shape and orientation. For instance, the U pentomino covers two of one color and three of the other, an imbalance of 1, while the T tetromino covers three of one and one of the other, an imbalance of 2.

For the whole board to be tiled, the signed imbalances of the twelve pieces must add up to the board's imbalance of \pm 1. That is a genuine necessary condition, a kind of conservation law for color. It will not by itself solve the puzzle, and working out the full table of signed contributions is a pleasant exercise left to the reader, but it illustrates the central habit of mathematical puzzle analysis: before you search for a solution, look for an invariant that any solution must obey. Sometimes the invariant proves a puzzle impossible. Here it merely narrows the corridor. Either way, it is cheaper than searching.

How hard is this, in general?

A sobering fact for the enthusiast: deciding whether an arbitrary set of polyominoes tiles a given rectangle is NP-complete. There is, in all likelihood, no algorithm that solves every such puzzle quickly, in the precise sense that the worst case grows faster than any polynomial. Our puzzle is not the worst case. It is tiny: twelve pieces, fifty-five holes, a few hundred candidate rows. For instances this small, well-guided backtracking does not merely work; it finishes before your finger leaves the Enter key. The art is in the guidance.

3. The Rust implementation, step by step

Exact cover says what a solution is. The Rust solver finds one by a simpler search than Knuth's dancing links: keep the board as the state, always fill the lowest empty hole (the anchor), and try every placement that covers that hole. The first empty hole must be covered by something in any completion, so every branch is a necessary choice, never a redundant one. Because pieces are always laid in the order their anchors appear, every finished board is reached by exactly one path through the tree. Combined with the counting invariant, success on a full board is a genuine solution.

The central engineering idea fits in one sentence: the entire 55-hole board lives inside a single 64-bit integer. Fifty-five holes need fifty-five bits, and a u64 has sixty-four, so there are nine bits to spare. Everything else in the file is a consequence of that decision.

const ROWS: usize = 5;
const COLS: usize = 11;
const CELLS: usize = ROWS * COLS; // 55
type Mask = u64;

A hole at row r and column c is identified with the bit at index r \cdot \texttt{COLS} + c, so the board is the integer whose set bits are the covered holes. A piece placement is also such an integer, its mask. Placing a piece is a bitwise OR. Detecting an overlap is a bitwise AND against zero. These are single instructions. The whole solver will run on bit arithmetic.

The piece definitions are relative coordinates. The first job is to expand each piece into all of its distinct orientations, which is exactly the D_4 orbit from the analysis.

fn normalize(mut cells: Vec<(i8, i8)>) -> Vec<(i8, i8)> {
    let min_r = cells.iter().map(|c| c.0).min().unwrap();
    let min_c = cells.iter().map(|c| c.1).min().unwrap();
    for c in &mut cells { c.0 -= min_r; c.1 -= min_c; }
    cells.sort();
    cells.dedup();
    cells
}

normalize slides a shape so its topmost, leftmost cell sits at the origin, then sorts and deduplicates. This gives every congruent copy of a shape a unique canonical representative, which is what lets us detect duplicates later. Two orientations that look the same after sliding will normalize to the same vector.

fn get_symmetries(cells: &[(i8, i8)]) -> HashSet<Vec<(i8, i8)>> {
    let mut seen = HashSet::new();
    let mut cur = cells.to_vec();
    for _ in 0..4 {
        seen.insert(normalize(cur.clone()));
        let mirrored: Vec<(i8, i8)> = cur.iter().map(|&(r, c)| (r, -c)).collect();
        seen.insert(normalize(mirrored));
        cur = cur.iter().map(|&(r, c)| (c, -r)).collect();
    }
    seen
}

This walks the dihedral group explicitly. The loop runs four times, once per rotation. In each pass it inserts the current rotation and its mirror image, then rotates 90° via the map (r, c) \mapsto (c, -r). That is the four rotations times the two reflection states — the full eight elements of D_4. The HashSet, whose elements are the normalized canonical forms, automatically collapses symmetric pieces down to their true orbit size. The U pentomino, with its mirror symmetry, yields four entries here, not eight, exactly as the orbit-stabilizer theorem predicted. The asymmetric F yields all eight. The group theory is now executable.

fn precompute_placements() -> Vec<Vec<(u8, Mask)>> {
    let mut placements: Vec<Vec<(u8, Mask)>> = vec![vec![]; CELLS];
    for (piece_id, vorm) in VORMEN.iter().enumerate() {
        let symmetries = get_symmetries(vorm);
        let mut piece_masks = HashSet::new();
        for shape in symmetries {
            let max_r = shape.iter().map(|c| c.0).max().unwrap();
            let max_c = shape.iter().map(|c| c.1).max().unwrap();
            for r in 0..=(ROWS as i8 - 1 - max_r) {
                for c in 0..=(COLS as i8 - 1 - max_c) {
                    let mut mask: Mask = 0;
                    let mut first_idx = usize::MAX;
                    for &(dr, dc) in &shape {
                        let idx = (r + dr) as usize * COLS + (c + dc) as usize;
                        mask |= 1 << idx;
                        if idx < first_idx { first_idx = idx; }
                    }
                    if piece_masks.insert(mask) {
                        placements[first_idx].push((piece_id as u8, mask));
                    }
                }
            }
        }
    }
    placements
}

This is the cleverest part of the program, and it is where the anchor heuristic gets compiled into a data structure. For every piece, every orientation, and every board position, it builds the placement's mask and, crucially, records the placement's smallest bit index, its first_idx. It then files the placement into placements[first_idx], the bucket for that index. The piece_masks set suppresses duplicate masks, so a symmetric piece that produces the same mask through two orientations is counted once.

Why index by the smallest bit? Because in the solver, the anchor will always be the smallest empty index, and any placement that could legally fill it must have that index as its own smallest cell. A placement whose smallest cell is below the anchor would necessarily cover an already-filled hole and is doomed. A placement whose smallest cell is above the anchor does not cover the anchor at all. So placements[anchor] is exactly the set of placements that can fill the anchor without an immediate, pointless collision. The expensive filtering has been done once, at startup, and the inner loop gets to iterate over a short, pre-vetted list.

fn solve(board: Mask, used_pieces: &mut [bool; 12],
         solution: &mut [Mask; 12], placements: &[Vec<(u8, Mask)>]) -> bool {
    let empty_idx = (!board).trailing_zeros() as usize;
    if empty_idx >= CELLS { return true; }
    for &(piece_id, mask) in &placements[empty_idx] {
        if !used_pieces[piece_id as usize] && (board & mask) == 0 {
            used_pieces[piece_id as usize] = true;
            solution[piece_id as usize] = mask;
            if solve(board | mask, used_pieces, solution, placements) {
                return true;
            }
            used_pieces[piece_id as usize] = false;
        }
    }
    false
}

Read this function slowly; it is the whole puzzle in twelve lines.

The first line finds the anchor. !board flips all 64 bits, so the zero bits of the board (the empty holes) become one bits. trailing_zeros is a hardware instruction — TZCNT or BSF on x86 — that returns the index of the lowest set bit in a single cycle. So (!board).trailing_zeros() is the index of the lowest empty hole, found in O(1), with no loop and no scan.

The base case is the guard bits doing their quiet work. If all 55 holes are filled, then bits 0 through 54 of the board are set and bits 55 through 63 are clear, so !board has its lowest set bit at position 55. The function returns 55, which is not less than CELLS, and we return true. The nine spare bits act as sentinels that guarantee the base case fires exactly when the board is full. By the counting invariant, full means solved, so returning true here is correct, not hopeful.

The loop iterates only over placements[empty_idx], the pre-vetted candidates that cover the anchor. For each, two guards apply. !used_pieces[piece_id] enforces the piece constraint — each piece at most once, which is the piece column of the exact cover matrix. (board & mask) == 0 enforces the no-overlap constraint: if the placement shares any bit with the current board, the AND is nonzero and we skip it. This single test is also the forward checking, because it catches any collision with holes that earlier pieces reached past the anchor.

Then the recursion. Note what is mutable and what is not. The board is passed by value as board | mask. It is never modified in place, so there is nothing to undo when the recursive call fails; the old board value simply reappears as the caller's stack frame resumes. The state that must be unwound, used_pieces, is the only thing mutated, and its undo is the single line used_pieces[piece_id] = false, the exact inverse of the line that set it. The solution array is written but never unwound, which is fine: on success we keep it, and on failure its stale entries are simply overwritten by later attempts before anyone reads them.

The main function is bookkeeping. It precomputes the placement table, runs the solver from an empty board (mask zero, all pieces unused), and, on success, decodes each piece's stored mask back into coordinates by testing each of the 55 bits, then paints a character grid for printing. The reconstruction loop is the inverse of the encoding: bit index i becomes row i / \texttt{COLS} and column i \bmod \texttt{COLS}.

Why is this fast enough to feel instantaneous? Four reasons compound. First, the anchor is found in one instruction instead of a scan. Second, the candidate list per anchor is precomputed and short, so the inner loop does almost no work. Third, every geometric test has collapsed into a bitwise AND, so the processor's wide execution units and fast paths do the heavy lifting. Fourth, and most importantly, the search tree itself is small, because the anchor heuristic admits no redundant paths and the overlap test prunes dead branches at the root. The bit tricks buy constant factors. The heuristic buys the exponent. It is worth being clear about which is which, because it is the heuristic, not the u64, that turns an NP-complete problem into a millisecond.

There is a satisfying circle here. The mathematics said the puzzle is an exact cover with a conservation law proving that full equals solved. The Rust solver encodes the board as an integer, the conservation law as a sentinel in the high bits, and the exact cover constraints as two bitwise tests, and in doing so makes the mathematics run at the speed of the hardware that was built to compute it. Twelve pieces, fifty-five holes, one integer. That is the whole trick.

---

The complete Rust source for this solver is in iqfit_solver.