Search feasibility

Search feasibility

yopl is a generic Prolog-style backtracking solver. It will faithfully explore every branch of whatever search tree your rules describe. That is also the trap.

Naïve encodings of combinatorial problems produce trees with O(N!) or O(branching^depth) leaf counts; per-call overhead in the proof loop (frame allocation + env push/pop + deep6 unification) makes exhausting those trees infeasible above modest N. This page documents the empirical wall on yopl 1.4.0, where it lands for typical workloads, and the two classes of fix.

When the naïve encoding is fine

If your search tree has effective branching < 4 and depth < 12, or if you only need the first solution and the encoding finds one quickly, naïve depth-first backtracking is what yopl is built for. The classic puzzle suite shipped in 1.4.0 (tests/test-hanoi.js, test-wgc.js, test-qsort.js, test-zebra.js) all complete in milliseconds with no heuristic tuning.

Sub-100ms ballpark on 2026-era hardware:

• Tower of Hanoi, 5 disks (31 moves enumerated): < 10 ms.
• Wolf/Goat/Cabbage (8-state space, BFS-equivalent depth 7): < 50 ms.
• Naïve quicksort of 12 elements: < 30 ms.
• Zebra puzzle (Einstein's-riddle variant, 15 constraints, unique solution): ~1 s — the second-solution check (asserting uniqueness) is what costs.

These are the encodings yopl handles fluently. The pattern is: explicit state, modest branching, a solution exists at moderate depth.

When you hit the wall

Two cases empirically exceeded reasonable time budgets:

Full 5×5 Knight's Tour from corner — > 6 min naïve, 13 ms with heuristic

tour(X0, Y0, N, Path) written as plain move/3 + visited-cell list + length-N check: explored more than 6 minutes without termination. The branching factor (up to 8 knight moves per cell, minus visited) and depth 25 produced a search tree that's nominally bounded but practically infinite at yopl's per-call cost.

Fix: Warnsdorff's heuristic (Warnsdorff 1823) + Pohl-style tie-break (prefer larger Manhattan distance to center) + cut-and-commit. The inline-JS goal walks the visited cons-list, computes onward-degree per candidate, returns a sorted cons-list of pair compounds; the clause body commits with Sorted = [pair(X2, Y2) | _], !. Result: 24 deterministic calls, ~13 ms for the full 5×5 open tour. See tests/test-knight.js::tour_w/3.

4×4 Sudoku enumerate-all-288 — > 120s naïve, fast with clues

Clue-laden mini-Sudoku puzzles (7+ clue cells) finish in tens of milliseconds because the clues prune most of the tree before search starts. But the blank-grid enumerate-all-288 problem — find every valid 4×4 Sudoku — generates 4¹⁶ ≈ 4 billion candidate grids before the row/column/box all_distinct constraints prune. Naïve fill_row + distinct exceeded the test-suite's 120s budget; that test was dropped from tests/test-sudoku.js.

The constraint isn't "Sudoku is hard"; it's "fill-then-test is exponentially wasteful." Interleaving member-with-all-distinct (constraint-and-generate) brings the same encoding back under budget — see the next section.

Mitigation 1 — encoding-side

If your problem has structure you can exploit, the encoding is where you fix it. yopl is a low-overhead generic engine; it has no constraint propagation, no clause indexing, no occurs-check elision. What it does have is ! (cut) and the ability to inline arbitrary JS for heuristic scoring.

The repertoire:

• Heuristic + cut-and-commit. Score candidates with an inline JS goal, sort, take the best, ! to commit. Turns O(branching^depth) into O(depth). Right when a good heuristic exists (Warnsdorff for knight; most-constrained-variable for CSP).
• Constraint propagation interleaving. Don't generate-then-test. Instead, interleave the constraint check with the choice — member(X, Domain), all_distinct([X, Y1, Y2, Y3]) rather than member(X, Domain), member(Y1, Domain), ..., all_distinct(...). Each choice immediately propagates against the partial solution, killing whole subtrees before they're walked.
• First-solution semantics with gen().next(). If you only need one solution, drive the search with gen() (the generator solver) and pull a single result. solve(rules, name, args, callback) exhausts the search tree regardless of what the callback does — the user callback is wrapped as env => (callback(env), false) to force backtracking on every solution. gen(rules, name, args).next() pauses after the first yield. The Knight's-Tour partial-tour test was the case study: 86,855 ms → 27 ms by swapping solve(...) for gen(...).next(), with no change to the rule encoding. See [solvers-gen](solvers-gen) for the API.
• Drop one of the dimensions. A 5×5 Knight's Tour is intrinsically harder than a 4×4. If your real workload doesn't need N=10, take N=8. The combinatorial wall is steep enough that one click smaller can collapse a multi-second search to instantaneous.

For most problems, encoding-side fixes are 10–100× wins and take an afternoon. Reach for them first.

Mitigation 2 — yopl-side (longer term)

If your encoding is already as tight as it gets and you're still hitting the wall, the bottleneck moves into yopl's per-call cost: proof-loop frame allocation, env push/pop, deep6 unification on every clause match. Reducing this is on the project queue but doesn't have a concrete plan yet.

Candidate levers (all speculative, none committed):

• Variable allocation pooling. generateVariables(count) mints count + 1 fresh variable(Symbol()) per clause attempt; under deep search this allocator dominates the per-call profile. A free-list / arena that reclaims on env.pop would lower the per-call cost. Risk: Symbol-name uniqueness has to be preserved.
• Faster cons-walk in assemble / deref. Walking deeply-nested cons lists touches one closure cell per node. A specialized walker that knows about {value, next} shape could be tighter. Risk: deep6 owns the walker; changes coordinate across both projects.
• Alternative IR backends. Three research items filed (see projects/yopl/queue in the vault — public mirror not yet up): IR → JS source codegen (eval'd or emitted as a module — may reach a different V8 JIT tier than the closure-factory shape), IR → WASM (WAM-style abstract machine; largest investment, boundary cost may dominate), and a leaner JS runtime as an IR target (trampolined / stack-machine — folds cut + backtrack into explicit opcodes). All three gated on the parity bench and cross-validation dogfood being stable enough to detect regressions automatically.

These are research-tier; don't budget on them. Encoding-side wins are the load-bearing answer for now.

solve vs gen().next() — same engine, different semantics

The four solvers (solve, solvers-gen, solvers-async, solvers-asyncGen) share one proof engine — they differ only in how they deliver solutions and whether they can await. For feasibility purposes, the relevant distinction is:

You want	Use
Every solution (enumeration)	solve(...) with callback
Side-effect on every solution	solve(...) with callback
The first solution and properties of it	gen(...).next()
Lazy enumeration with early break	gen(...) in for...of
Composition with iterator utilities	gen(...)
Async result handler / await per result	solversAsync*

solve has no early-exit mechanism — the user callback's return value is ignored (the wrapper hard-codes false to force backtracking). If your test code reads if (!result) { result = ...; } and then asserts on result, you've written an enumerate-all where you meant first-solution. Switch to gen(...).next().

This is purely a driver choice; the underlying rules don't change. The same tour/4 rule that took 86 s to enumerate under solve(...) returned the first solution in 27 ms under gen(...).next(). See logs/2026-05-10-yopl-test-suite-profiling.md in the vault for the diagnostic walkthrough.

See also

• solve — push-style enumeration entry point.
• solvers-gen — pull-style generator driver.
• Writing-rules — how to express the encoding-side mitigations.
• Using-deep6 — the per-call cost model (env push/pop + unify).