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.
Meet in the middle is the oldest exponent-cutting trick in combinatorial search: instead of exploring one tree of depth , explore two trees of depth and join their leaves on a shared interface. Ellis Horowitz and Sartaj Sahni introduced it in 1974 for the knapsack problem, turning time into time, at the price of storing one half's results in a table keyed so the other half can look them up. The same idea resurfaces as the meet-in-the-middle attack in cryptanalysis (why double DES buys almost nothing over single) and as bidirectional search in pathfinding. The pattern is always the same: two cheap enumerations plus a join, instead of one impossible enumeration.
Eternity II offers a natural cut: a horizontal seam. Take a band of rows to finish; split it into a top half and a bottom half. Enumerate every way to fill the top half, keyed by two things: the exact set of pieces it consumed, and the vector of edge colours it leaves dangling at the seam. Enumerate the bottom half symmetrically. Then join: any top and bottom whose seam colours agree and whose piece sets are disjoint form a complete filling, found without ever walking the full band's tree.
The disjointness clause is the E2-specific pain, and it is not optional. In knapsack the two halves are independent by construction; here they draw on one shared pool of pieces, so tops must be grouped by their exact pool fingerprint and each group joined only against bottoms built from the complementary pieces. Skip that bookkeeping and the join happily produces phantom boards that use a piece twice. Getting exact complementary-pool accounting right was a hard-won correctness lesson of the project's experiment below.
The textbook trade is time for memory: the exponent halves, and one half's enumeration must be held in a hash table. On the board the interface state is a row of edge colours (16 cells wide on the full puzzle) plus the pool fingerprint, so the table's key space grows fast with band width, and memory, not time, is usually the first wall. The join itself is cheap (hashing); everything hinges on how many entries each side must store and on how often seam signatures actually coincide.
Numbers pin down the trade in a way prose cannot. The lab below has two views. The trade puts the three bills side by side on a log scale as you grow the problem: one-sided time , MITM time , MITM memory table entries. The join runs a complete micro-instance (, two halves of candidates each) through the store phase and the probe phase, so you can watch where the speed comes from and where the memory goes.
The classic Horowitz–Sahni accounting, for a problem of binary choices:
(plus a factor if the halves are sorted rather than hashed). Note what is conserved: the product of time and space stays around . Meet in the middle never destroys the exponential; it splits one unpayable bill into two smaller ones, and both must clear. The square root of the runtime is bought with an exponential memory bill, which is why the method wins exactly when entries still fit in RAM and loses the moment they don't.
On Eternity II the clean -choices model needs two corrections. First, the interface is not one number but a wide state (a seam vector of up to 16 edge colours plus the exact piece-pool fingerprint), so the table keys are big, entries are fat, and the memory wall arrives well before the textbook crossover. Second, the halves are coupled through the shared piece pool, so the join is not a free hash hit but a hash hit filtered by complementary pools. BANDSAW measured the consequence: within small mismatch budgets both sides stay enumerable and the method is exact, but each extra budget unit inflates both trees roughly twenty-fold per side, and near the horizon the project paid for millions of stored tops whose buckets no bottom ever probed successfully.
This project ran the idea to the end, rigorously, in the BANDSAW experiment: exact best completion of a band, meet-in-the-middle join with exact pool accounting, iterative deepening on the mismatch budget, all validated on a 10×10 testbed against brute force. Three findings, measured on this project's engine and not independently replicated:
The general lesson matches the classic literature: meet in the middle wins when the interface is narrow, the halves are truly independent, and a solved/unsolved answer suffices. Eternity II strains all three: the seam carries a wide colour vector, the shared piece pool couples the halves, and the record game runs on partial credit, which re-inflates both trees. What remains genuinely untested here is the heuristic cousin: two beams growing from opposite edges of the board, cross-filtered by hashes of their seam colours, meeting at a middle row. That design was written down in this project but never run; whether bidirectional pruning helps a beam the way it fails an exact join is an open question, not a verdict.