# BANDSAW > Solve a band of rows exactly by meeting in the middle, to find the true best ending and to measure how far ahead an endgame can be decided. - Canonical page (with interactive figures/demos): https://eternity2.dev/research/lab/experiments/raphael-anjou/meet-in-the-middle/bandsaw/ - Updated: 2026-07-21 - Topics: exact-methods - Source: Meet-in-the-middle (this project's concept page): the two-halves-and-join technique — https://github.com/raphael-anjou/eternity2/blob/main/web/content/research/build/exact/meet-in-the-middle.mdx --- 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. ## How it works 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. > **[Figure]** Interactive: the meet-in-the-middle endgame tree — interactive: MeetInMiddleDiagram. Rendered on the canonical page (link above); not shown in this markdown export. ## The result 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. ## Method 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](/research/build/exact/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. ## Reproduce 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. ## Open questions 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? ## Related - [STAGED](https://eternity2.dev/research/lab/experiments/raphael-anjou/pipelines/staged) — Build the whole board from scratch with no pre-set frame, in stages, letting the border emerge last from whatever pieces are left. - [Entropy and the area law](https://eternity2.dev/research/why/entropy-area-law) — Eternity II has two rules: edges must match, and each piece is used once. The first is generous. All the hardness lives in the second. - [Meet in the middle](https://eternity2.dev/research/build/exact/meet-in-the-middle) — Enumerate two halves of a problem and join them on a shared interface, trading memory for an exponent cut in half. The classic Horowitz–Sahni trick, what it looks like on bands of the board, and what this project's BANDSAW experiment measured, including the one-sided method that beat it.