# 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. - Canonical page (with interactive figures/demos): https://eternity2.dev/research/build/exact/meet-in-the-middle/ - Updated: 2026-07-02 - Topics: exact-methods - Source: Horowitz & Sahni 1974, "Computing Partitions with Applications to the Knapsack Problem" (JACM), the classic origin — https://doi.org/10.1145/321812.321823 - Source: Meet-in-the-middle attack (Wikipedia), the cryptanalytic branch of the same idea — https://en.wikipedia.org/wiki/Meet-in-the-middle_attack - Source: Bidirectional search (Wikipedia) — https://en.wikipedia.org/wiki/Bidirectional_search --- Meet in the middle is the oldest exponent-cutting trick in combinatorial search: instead of exploring one tree of depth $n$, explore two trees of depth $n/2$ and join their leaves on a shared interface. Ellis Horowitz and Sartaj Sahni introduced it in 1974 for the knapsack problem, turning $O(2^n)$ time into $O(2^{n/2})$ time, at the price of storing one half's $2^{n/2}$ 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. ## What it looks like on the board 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 trade 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. ## Feel the square root 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 $2^n$, MITM time $2 \cdot 2^{n/2}$, MITM memory $2^{n/2}$ table entries. *The join* runs a complete micro-instance ($n = 10$, two halves of $2^5 = 32$ candidates each) through the store phase and the probe phase, so you can watch where the speed comes from and where the memory goes. > **[Figure]** Interactive: meet-in-the-middle memory cost — interactive: MitmCostLab. Rendered on the canonical page (link above); not shown in this markdown export. ## Step by step 1. **Drag $n$ in the trade view.** Every $+2$ on the slider *quadruples* the red one-sided bar but only *doubles* the two MITM bars. That factor-of-two difference in growth rate is the entire trick: the exponent is halved, so on a log scale the MITM bars climb at half the slope. 2. **Watch the memory bar arrive.** Around $n \approx 56$ the table (at an optimistic 16 bytes per entry) outgrows a 16 GiB machine, while the MITM *time* bar is still comfortable. Memory hits the wall first: the same order of events BANDSAW recorded, where real entries carry a pool fingerprint and a seam vector and are far fatter than 16 bytes. 3. **Switch to the join view.** The left half enumerates its 32 candidates and stores each one in a hash table keyed by its seam signature (one of 48). This is the phase that pays the memory bill: the counter under *table memory* is the bill arriving, entry by entry. 4. **The probe phase.** The right half's 32 candidates arrive one per tick, and each performs exactly one lookup. An empty bucket dismisses an entire family of combinations in one step; an occupied one yields a joined solution per stored partner, found without walking the full tree. 5. **Read the final tally.** $2 \cdot 32 = 64$ enumeration steps plus $32$ stored entries replace $2^{10} = 1{,}024$ full walks. On Eternity II the same arithmetic holds, with the caveat that a join only counts if the seam colours match *and* the piece pools are disjoint, which is what the grouping-by-fingerprint bookkeeping above is for. ## What it costs The classic Horowitz–Sahni accounting, for a problem of $n$ binary choices: $$ \underbrace{O(2^n)\ \text{time},\ O(n)\ \text{space}}_{\text{one-sided enumeration}} \quad\longrightarrow\quad \underbrace{O(2^{n/2})\ \text{time},\ O(2^{n/2})\ \text{space}}_{\text{meet in the middle}} $$ (plus a $\log$ factor if the halves are sorted rather than hashed). Note what is conserved: the *product* of time and space stays around $2^n$. 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 $2^{n/2}$ entries still fit in RAM and loses the moment they don't. On Eternity II the clean $n$-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. ## What BANDSAW measured This project ran the idea to the end, rigorously, in the [BANDSAW experiment](/research/lab/experiments/raphael-anjou/meet-in-the-middle/bandsaw): 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: - **It works, near perfection only.** Within small mismatch budgets the method is exact and affordable. But each unit of mismatch budget inflates the enumeration trees roughly twenty-fold *per side*, so the regime where exactness is payable dissolves within a handful of allowed defects. - **A one-sided method beat it.** Armed with the same exact lower-bound tables (min-plus suffix bounds computed column by column), a plain iterative-deepening branch-and-bound proved optimality in about 12 seconds on a rung where the bidirectional join did not finish. The MITM pays full enumeration of *both* halves even when a single optimum plus an exhaustion proof would do; near the decidability horizon its join almost never fired: millions of stored tops, zero matching bottoms, both bills paid for nothing. - **The durable outputs were the bounds.** What survived the experiment was not the join but the admissible lower-bound tables and the exact budget-certificates they enable, instruments now used elsewhere. The registered conclusion was blunt: no meet-in-the-middle deployment at full board size. ## Limits, and what is still open 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. ## Related - [BANDSAW](https://eternity2.dev/research/lab/experiments/raphael-anjou/meet-in-the-middle/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. - [CLOISTER](https://eternity2.dev/research/lab/experiments/raphael-anjou/pipelines/cloister) — Fix a perfect border, then search the interior with the border's edges treated as hard constraints from the very first cell. - [Exact cover and dancing links](https://eternity2.dev/research/build/exact/exact-cover-dlx) — Eternity II states cleanly as an exact-cover problem, and Knuth's Algorithm X with dancing links is the classic machine for those. Where it genuinely shines (small boards, exhaustive counting) and the two reasons it does not crack the 16×16: an unshrunk search tree, and no partial credit. - [Dead ends](https://eternity2.dev/research/build/dead-ends) — Approaches we tried that look promising and don't move the needle on Eternity II, written down with what we found so you can spend your time elsewhere.