Searching for Bricks

Bricks asks the question: is there a brick with exactly one way to tile some pyramid? This page is about script that evaluates bricks — and how it only needs to fully evaluate 750 of 65,536 bricks.

For each brick we assess the number of solutions from an infinite supply of that one brick and an specific empty volume. We are interested in the answers "none, one, or more than one" so we stop after we find the second solution.

Where the time goes

Bricks with many solutions are fast- find two solutions and exit early. But bricks with zero solutions are even faster, because we can prune down so much of the decision tree (eg: if you can't place a second brick, you can exit very quickly).

Every brick costs about the same, whatever its answer, and every search is tiny — a hundred steps or so. The work is not in exploring a big space; it is in the fixed price of setting up and taking any step at all, and a brick that fits pays it just as surely as one that doesn't.

That rules out the obvious optimizations. Better pruning saves nothing when there is barely a tree to prune. The only lever left is to run the solver on fewer bricks.

Optimization 1: chain across the levels

The first cut was already there. A brick that cannot tile pyramid(N-1) cannot tile pyramid(N) either — the board only grows — so each level only evaluates what survived the level below.

Each level inherits a smaller pool than the last. The bricks are the same 16,576 canonical codes throughout; what shrinks is how many of them are still worth asking about.

Optimization 2: skip what is already ruled out

The No Unique Solutions round proves that certain bricks can never have exactly one solution on any pyramid. The sweep used to search them anyway, and then the page threw the answer away.

It now skips them. There is a distinction worth being careful about, though: that round produces two sets, and only one is an elimination.

The post-heavy bricks are not skipped. That rule rules them out of its own claim while explicitly deferring to these sweeps to measure how far they actually reach, so skipping them would delete the measurement it is deferring to.

Every run now reports its skips up front, before any searching starts:

Skip pass — 12637 of 16576 canonical brick(s) will not be searched:
   12107  no solution on the previous pyramid level
     530  proven never to have exactly one solution
         209  bottomSymmetricTopNot
         170  topSymmetricBottomNot
          76  topNoPosts
          75  bottomAllHoles
    3939  left to evaluate.

Optimization 3: one brick's answer settles another's

Bricks are partially ordered by how hard they are to fit. Adding a post can only ever rule placements out; removing a hole can only ever rule placements out. So if brick B has all of A's posts and none of the holes A lacks, B is at least as hard to place as A, everywhere, on every board.

Both halves collapse into a single 16-bit number — posts in the high byte, inverted holes in the low byte — and then "harder than" is just a subset test.

Inverting the holes is what turns "more posts and fewer holes" into one direction. Comparing two bricks costs a single bitwise AND.

Two rules follow, and each settles a brick without searching it:

No solutions propagates upward. If a brick has no solutions, nothing harder does either.
Two-or-more solutions propagates downward — with one exception.

The exception

Rule 2 is not true as stated, and the way it fails is worth seeing, because it fails exactly on the bricks this whole investigation is looking for.

Both bricks tile pyramid2 on exactly one carving — three upright 2×4 blocks with one 4×2 on top — and on it all four pieces can be turned 180° in place. 1900's posts are not symmetric under that turn, so each of the 2⁴ combinations looks different and counts separately: sixteen solutions. 1800's posts are symmetric, so the turn changes nothing visible and all sixteen collapse into one.

Removing a post never removes an arrangement. It can remove the distinction that made two arrangements count separately.

The same symmetry shows up on both sides of this page. 1900 is excluded by optimization 2 under the rule bottomSymmetricTopNot — its holes are half-turn symmetric and its posts are not, which is exactly why turning a piece rearranges what you can see and multiplies its solution count. 1800 is the mirror case, and the grid below shows it as one of the 750 bricks the solver actually had to run. That is the guard working: the bricks it withholds rule 2 from are precisely the ones whose answer cannot be guessed.

So rule 2 carries a guard: a brick may only inherit "two or more" from a harder brick unless it is more symmetric than that brick. The guard costs almost nothing, because half-turn symmetry is rare: the turn pairs the eight cells into four two-cycles with no fixed point, so only 16 × 16 of the 65,536 codes survive it.

Optimization 4: walk the frontier

The rules only ever settle a brick from one side. Some bricks can't be reached from either — the minimal non-fitting bricks and the maximal fitting ones, the boundary between fits and doesn't. Every one of those has to be searched by any strategy at all, and nothing else strictly has to be.

So the order matters, and it is worth more than it looks.

Solving in plain ascending order wastes searches in the middle of regions the rules would have settled anyway. The frontier walk seeds on the most central unsettled brick, then steps one bit at a time toward whichever side the last answer pointed — staying on the boundary rather than starting over from the middle. A balanced-split heuristic, which sounds better, does worse than either: it maximises information per query rather than aiming at the boundary, and the boundary is the only thing that must be paid for.

What actually got searched

Every canonical brick on the two-level pyramid, coloured by how its answer was arrived at. The layout is the candidate map's: posts across, holes down.

Orange is the only colour that costs anything. It traces the boundary between the region that fits and the region that doesn't, which is precisely where the unavoidable work lives.

What it adds up to

The gains shrink as the boards grow, and that is the honest shape of it. Bigger pyramids have proportionally more boundary and fewer interior bricks for the rules to sweep up, so a larger share of the pool has to be searched for real.