Search: Backtracking, Branch-and-Bound, Binary Search, Meet-in-the-Middle
How to explore an exponential space without visiting all of it - plus the computational geometry predicates that let you prune in the plane.
Leads to: 19.14 turns pruning into a feasibility estimate. The Euler Lab’s Search & Geometry problems (magic squares, Sudoku-like puzzles, lattice/triangle geometry) live here.
Learning Objectives
Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.
- Implement backtracking with constraint propagation and explain how pruning changes the effective branching factor.
- Add an admissible bound to convert backtracking into branch-and-bound and prove the bound never discards an optimum.
- Use binary search on the answer (parametric search) and state the monotone predicate it requires.
- Implement meet-in-the-middle and derive its \(O(2^{n/2}n)\) cost.
- Compute the 2-D orientation and point-in-triangle predicates exactly in integers, and use them to prune geometric searches.
Key Vocabulary
- Backtracking
- DFS over partial solutions; extend, test feasibility, and undo. The gain comes entirely from failing FAST.
- Pruning / constraint propagation
- Discarding a partial solution the moment it cannot be completed. Reduces the effective branching factor, not the worst-case exponent.
- Branch-and-bound
- Backtracking + an admissible bound on the best completion; prune any branch whose bound is worse than the incumbent.
- Binary search on the answer
- When \(P(x)\) is monotone in \(x\), find the threshold in \(O(\log\text{range})\) evaluations. Also called parametric search.
- Meet in the middle
- Split the input in half, enumerate both halves (\(2^{n/2}\) each), and join by sorting/hashing. Turns \(2^n\) into \(2^{n/2}\log\).
- Orientation predicate
- The sign of the cross product \((b-a)\times(c-a)\): +, 0 or − for counter-clockwise, collinear, clockwise. Exact in integer arithmetic.
- Shoelace formula
- The area of a polygon from its vertices: \(2A=\big|\sum_i (x_iy_{i+1}-x_{i+1}y_i)\big|\) - integer-exact for lattice polygons.
Intuition & Motivation
Backtracking and pruning
The template: maintain a partial assignment; at each level, try every legal extension; recurse; undo. The only lever is the legality test - the earlier you can prove that a partial solution is doomed, the more of the tree disappears.
Branch-and-bound
The admissibility requirement is what makes pruning safe: because the bound never overestimates, discarding a branch can never discard an optimum. A tighter bound prunes more but costs more to compute - the design trade-off is entirely about that balance. (This is the same optimism condition as the \(h\) heuristic in A*.)
Binary search on the answer
The art is inventing the predicate. ‘What is the minimum capacity that allows the shipment in \(D\) days?’ is hard; ‘does capacity \(c\) suffice?’ is easy and monotone. Turning an optimisation into a decision problem, then bisecting, is one of the highest-yield moves in competitive mathematics.
Meet in the middle
For \(n=40\): \(2^{40}\approx1.1\times10^{12}\) becomes \(2\times2^{20}\approx2\times10^6\) enumerations plus a sort. The price is \(O(2^{n/2})\) memory. It applies whenever the objective decomposes additively across the two halves - subset sums, \(x^a+y^b=T\) searches, 4-sum, and discrete-log baby-step/giant-step.
Computational geometry: exact predicates, then prune
Geometric search (lattice triangles, convex hulls, point location) is search plus a handful of predicates. Compute them in integers (19.4) - the sign of a determinant is a discrete fact and must never be decided by a float.
Its sign is +1 if \(a\to b\to c\) turns counter-clockwise, 0 if collinear, −1 if clockwise. From it you get, with no divisions and no floats:
- Point in triangle: \(p\) is inside \(\triangle abc\) iff \(\operatorname{orient}(a,b,p),\ \operatorname{orient}(b,c,p),\ \operatorname{orient}(c,a,p)\) all have the same sign (allow zeros for boundary).
- Segment intersection: \(ab\) and \(cd\) properly cross iff \(\operatorname{orient}(a,b,c)\) and \(\operatorname{orient}(a,b,d)\) have opposite signs, and likewise for \(c,d\) against \(a,b\).
- Area (shoelace): \(2A=\big|\sum_i(x_iy_{i+1}-x_{i+1}y_i)\big|\) - and note \(2A\) is an integer for lattice polygons, so you can test ‘is the area an integer?’ or ‘is it zero (degenerate)?’ exactly.
- Pick’s theorem: for a lattice polygon, \(A=I+\tfrac B2-1\) with \(I\) interior and \(B\) boundary points, and \(B=\sum_i\gcd(|\Delta x_i|,|\Delta y_i|)\) - a gcd (19.1) counting lattice points on each edge.
Coding workbench
The Euler Lab’s Search & Geometry problems reward exactly this instinct: before enumerating, ask whether the space can be halved (binary search), split (meet-in-the-middle), or pruned (backtracking with a bound). And in the geometry problems - lattice triangles containing the origin, right-triangle counts, convex-hull questions - the winning move is always an integer predicate, never a float.
- Backtracking without incremental feasibility checks: testing a full assignment at the leaves throws away the entire benefit.
- Using a bound that is not admissible (it overestimates the best completion). You will prune the optimum and never know.
- Binary-searching a non-monotone predicate. Bisection is only valid on a monotone (or unimodal, for ternary search) landscape.
- Meet-in-the-middle without enough memory: \(2^{n/2}\) for \(n=50\) is 33 million entries - check the memory before the clock.
- Deciding geometric predicates with floats. orient returning 1e-17 instead of 0 makes three collinear points a triangle and silently corrupts a convex hull.
- Order your branching by the most constrained variable first (fewest legal values). This one heuristic often beats a cleverer algorithm.
- Turn optimisation into decision, then bisect. ‘Minimise X’ is hard; ‘is X ≤ c achievable?’ is often easy and monotone.
- Meet-in-the-middle is the standard rescue when \(n\approx40\): too big for \(2^n\), too small for a polynomial algorithm to exist.
- Keep all lattice geometry in integers; multiply through by denominators rather than dividing. Twice the area is an integer - use \(2A\) as your quantity and never divide.
Practice this in the Euler Lab
Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.
Warm-up:
#6 Sum Square Difference (1%, tier A) #9 Special Pythagorean Triplet (1%, tier A) #28 Number Spiral Diagonals (2%, tier A) #39 Integer Right Triangles (2%, tier A)
Applied:
#293 Pseudo-Fortunate Numbers (16%, tier B) #504 Square on the Inside (16%, tier B) #265 Binary Circles (17%, tier B)
Challenge:
#147 Rectangles in Cross-hatched Grids (41%, tier C) #161 Triominoes (41%, tier C)
322 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.
Knowledge Check
Practical Exercise
(a) You must find the smallest side length \(s\) such that a certain packing fits. Testing a given \(s\) costs \(O(n\log n)\) and is monotone. Give the total cost of finding \(s\) to integer precision in \([1,10^9]\). (b) Count how many lattice triangles with vertices among \(\{0,\dots,3\}^2\) contain the origin strictly inside - describe the exact-integer algorithm (do not enumerate by hand). (c) Use Pick’s theorem to find the number of interior lattice points of the triangle \((0,0),(6,0),(0,9)\).
(a) Binary search on the answer: the predicate ‘does side \(s\) fit?’ is monotone (if \(s\) fits, so does anything larger), so bisection over \([1,10^9]\) needs \(\lceil\log_2 10^9\rceil=30\) evaluations. Total \(O(30\cdot n\log n)\) - i.e. 30 times the cost of a single feasibility check. The optimisation is no harder than the decision, up to a log factor.
(b) Enumerate all \(\binom{16}{3}=560\) triples of the 16 lattice points. For each, compute the three orientations \(\operatorname{orient}(a,b,O),\ \operatorname{orient}(b,c,O),\ \operatorname{orient}(c,a,O)\) by (19.21) in exact integers. The origin is strictly inside iff all three signs are equal and none is zero (a zero means the origin lies on an edge line). Degenerate (collinear) triples are excluded automatically because their own orientation is 0. Cost: \(O(\binom{16}{3})\) with 3 integer determinants each - trivially fast and exactly correct. (For the record, with the origin as a corner of this grid no triangle can contain it strictly inside; the algorithm is what matters, and it is the one you would run on a million random triples.)
(c) Vertices \((0,0),(6,0),(0,9)\). Area by shoelace: \(2A=|0\cdot0-6\cdot0 + 6\cdot9-0\cdot0 + 0\cdot0-0\cdot9|=54\), so \(A=27\). Boundary points: each edge contributes \(\gcd(|\Delta x|,|\Delta y|)\) - \(\gcd(6,0)=6\), \(\gcd(6,9)=3\), \(\gcd(0,9)=9\) - so \(B=6+3+9=18\). Pick: \(A=I+\tfrac B2-1\Rightarrow 27=I+9-1\Rightarrow I=19\). Nineteen interior lattice points - obtained with two gcds and one integer determinant, no floating point anywhere.
Lesson Summary
Retrieval Practice
Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.
A: Admissibility: it must never be worse (for minimisation, never larger) than the true best completion. Then a branch whose bound already loses to the incumbent cannot contain the optimum, so pruning it is safe.
A: \(O(2^{n/2}n)\) time, \(O(2^{n/2})\) memory. It requires the objective to decompose ADDITIVELY across the two halves, so that half-results can be joined by sorting/hashing.
Completion Checklist
- I can explain the core ideas in my own words
- I worked the derivations/examples by hand
- I completed the interactive workbench(es)
- I passed the knowledge check
Source References
This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.
- The Pragmatic Programmer (Thomas & Hunt, 2nd/20th Anniv. ed., 2019) current - Ch. 4 & Ch. 7 - Search as engineering: fail fast, prune early, and test the pruned search against an unpruned brute force on small instances to prove you did not prune the answer away.
- Additional Exercises for Convex Optimization (Boyd & Vandenberghe, 2016) current - Branch-and-bound / relaxation exercises - Branch-and-bound and relaxation-based bounds for non-convex problems - the optimisation-theory home of admissible bounding.
- Numerical Linear Algebra (Trefethen & Bau, SIAM, 1997) foundational - Lectures 12–15 - Why a geometric predicate must be decided exactly: conditioning of a nearly-singular determinant, and the meaning of a computed sign.