Reproducedeterministic — reproduces byte-for-byte·reruns the search (See below)·Budget: deterministic exact analysis; the committed example reproduces byte-for-byte
Complexity
Time
meet-in-the-middle: ~√ of the naive enumeration; but each half grows ~20× per extra mismatch budget
Space
O(number of top-half partials), the seam/piece-set hash table is the memory bottleneck
Meeting in the middle trades time for space: it replaces one exponential walk with two smaller ones plus a join, which is why the band size is capped by memory, not time.
Hardware & run
Native runCPU only
Cores
8
RAM
16 GiB
GPUs
0
CPU
Apple M1
Machine
MacBook (Apple M1, 8 cores)
Budget
deterministic exact analysis; the committed example reproduces byte-for-byte
Heuristic search guesses; it never knows it has the best possible finish.
BANDSAW is the opposite experiment: for a band of rows near the bottom, it
computes the exact best completion, with a proof that nothing scores higher.
The aim isn't speed, it's certainty, and the certainty doubles as a ruler
for how hard the endgame really is.
Split the band into a top half and a bottom half. Enumerate every way to fill
the top half up to a small mismatch budget, keyed by two things: which pieces
it used, and the row of colors it leaves dangling at the seam. Enumerate the
bottom half the same way, but only from the pieces the top half didn't use.
Then join the two halves wherever their seam colors agree and their piece
sets don't overlap. That meet-in-the-middle join finds the exact best
completion without walking the whole tree.
Exact lower-bound tables, computed by working backwards column by column, let
it prune branches that already can't beat the budget, and it raises the
budget step by step until a round finds nothing new, which proves the best
score for that band.
▶Interactive: the meet-in-the-middle endgame treeExplore →
On a 10×10 testbed BANDSAW settles the endgame exactly and pins the budget
where exactness stops being affordable: the search tree grows about
twenty-fold per extra mismatch, on both sides, so meeting in the middle stops
paying off at full board size. That negative is the useful part: it tells you
exactly where exact methods give out and heuristics must take over. The exact
pieces that survived, the suffix lower-bound tables and the pruned
branch-and-bound, became reusable instruments. A frame-free board scoring 437
came out of the same machinery.
The join is the idea; the pruning is what makes it affordable.
Meet in the middle. Split the band into a top and bottom half. Enumerate
every top-half fill up to a mismatch budget, keyed by (piece-set used, seam
colour row). Enumerate the bottom half the same way, drawing only from the
pieces the top half left. Join two halves wherever their seam colours agree
and their piece-sets are disjoint. That join finds the exact best
completion without ever walking the full tree, the classic
meet-in-the-middle time-for-
space trade.
Suffix lower bounds. Working backwards column by column builds exact
lower-bound tables, so a partial that already cannot beat the current budget
is pruned before it is extended.
Budget ratchet. Raise the mismatch budget one step at a time and re-solve;
when a round finds nothing better, the previous best is proven optimal for
that band. That proof is why this page is tagged proven, not measured:
the result is a certificate, not a sample.
The measured ceiling: each half grows ~20× per extra unit of budget, so at full
16×16 board size the top-half table no longer fits, memory, not time, is the
wall. That negative is the deliverable: it pins exactly where exact methods give
out and heuristics must take over. The frame-free 437 board fell out of the same
machinery.
Deterministic (kind: exact): the meet-in-the-middle solve and its optimality
proof reproduce byte-for-byte for a given band, and the 437 board is checkable
in the viewer. The MITM enumerator and suffix-bound tables are committed with
the research code.
Can the lower-bound tables scale to the full 16×16 endgame, or does the seam
state space grow too large? At what band size does memory rather than time
become the limit? And can the rare cases where the middle join does fire be
spotted in advance and finished exactly?