extSearch
A compilation of heuristic solutions to hard algorithmic problems
Overview
It's been nearly 2 years to the date since I've last done a larger-scale project, and while I have had a few plans to do so once I have graduated, I've been allowed the opportunity to work on a project that I have been fairly invested in creating.
The first flagship problem is packing n unit squares into the smallest possible enclosing square.
Given a number of unit squares, the goal is to minimize the container side length, usually written as
s(n).
Square Packing, Visually
The problem looks simple at first, but becomes highly geometric very quickly. For small values of n,
axis-aligned layouts are often optimal. For many larger values, rotated squares are required.
Below, two catalog SVG packings are shown side by side. Each diagram uses the same mathematical units:
unit squares have side length 1, and the outer frame has side s. The figures are laid out so
the on-screen width of each outer square is proportional to its s(n) (flex growth uses
the same numeric s as in the SVG). That way you can compare how much larger a best-known
container for n = 17 is than the proved-optimal n = 10 case.
\(s = 3 + \tfrac{1}{2}\sqrt{2} \approx 3.707\) (proved optimal). Minimal rotated squares; related to adding an “L” to \(s(5)\).
\(s \approx 4.676\) (best known at time of diagram; defined by a degree-18 polynomial root). Found by John Bidwell (1998).
Source files: square-10b.svg, square-17.svg (same coordinate convention as
Squares in Squares).
Even a single tilted square creates nonlinear geometric constraints, and each additional square introduces many more possible placements and interactions.
Reference Catalog: Best Known Packings
The most complete public catalog I use is David Ellsworth's
Squares in Squares.
It records best-known packings across many values of n, often with:
- the current best-known side length
s(n), - whether the value is proved optimal or still a computational record,
- the discoverer, date, and improvement history,
- SVG configurations that make geometric structure inspectable.
The labels are important: some entries are fully proved, while others are currently best-known constructions awaiting proof of optimality.
Live Link
Open the full database here: https://kingbird.myphotos.cc/packing/squares_in_squares.html
If your browser blocks embedding for this page, use the direct link above.
How "Optimal" Is Documented
In this area, there are two tiers of results:
- Proved optimal: there is a mathematical argument that no smaller container can exist.
- Best known: a construction is currently the strongest found, but not yet ruled unbeatable.
A lot of progress happens in the second tier first: search finds a better packing, then proof work tries to close the gap and certify optimality.
Why This Is Hard (NP-Hard Intuition)
Related rectangle/square packing decision variants are NP-hard, and this optimization form inherits the same
combinatorial explosion. The challenge is not just "where to place squares," but "which of many interacting
geometric constraints can all be satisfied at once" while minimizing s(n).
In practice, exact search scales poorly because:
- the number of combinatorial layouts grows rapidly with
n, - allowing rotations adds continuous (angle/position) dimensions,
- feasibility checks involve nonlinear overlap and boundary constraints.
Why extSearch Uses Heuristics
Heuristics are the practical way to make progress now. Instead of requiring full exact proofs up front, we can generate high-quality candidate packings fast, compare methods, and iterate on strategies.
My goal is to make extSearch useful for three parallel tracks:
- Interest: make the problem approachable and visually engaging for more people.
- Data: collect user runs, near-miss layouts, and successful move sequences at scale.
- Proof pipeline: use that corpus to guide conjectures, symbolic analysis, and AI-assisted proof attempts.
From Heuristics to Proofs
Every strong heuristic solution is a hypothesis about structure. Repeated patterns from users and algorithms can expose invariants, bottleneck constraints, and candidate lower bounds. Those are exactly the ingredients needed to move from "best-known" to "proved optimal."
Long term, I want extSearch to function as both a solver and a research dataset: humans explore, heuristics propose, and AI systems mine the resulting geometry for proof ideas.
Conclusion
Square packing sits at a great intersection of visual intuition, hard complexity, and open mathematical questions. extSearch is my attempt to turn that into a collaborative platform.
I expect to step away from day-to-day work on extSearch after the semester ends. The project lives on GitHub as open source software with documentation for anyone who wants to run it, extend it, or take the ideas in a different direction. If that sounds like you, you are welcome to pick it up.