roadmap: improve time to the first square solution #16
No Assignees
Notifications
Due Date
No due date set.
Dependencies
No dependencies set.
Reference: mgrettondann/partridge-cpp#16
Reference in New Issue
Block a user
Objective
Coordinate the work needed to reduce the time required to find one solution to a square Partridge puzzle. Rectangular puzzles and solution enumeration are out of scope.
The general packing problem remains exponential in the worst case, so work should first remove unnecessary searches, then reduce the search tree, and only then reduce per-node cost or add parallel hardware.
Working rules
Recommended order
Phase 0: establish correctness and measurement
Establish CTest and an independent validator for dimensions, multiplicities, bounds, overlap and complete coverage. Add only the minimum harness needed for the two bug regressions first; expand the suite incrementally.
ResultsDebug assertion.This unblocks Debug builds and assertion-enabled tests.
This removes the sanitizer-confirmed heap-buffer overflow. Record a failing sanitizer regression before fixing it.
Record a clean baseline only after #7 and #14 are fixed. Keep benchmark timing separate from correctness tests.
Gate A: Debug and sanitizer configurations pass, solutions are independently validated, and a reproducible single-thread baseline exists.
Phase 1: take the guaranteed reduction
This avoids direct exponential search for every odd order at least 9 and should be implemented before tuning order-9 search.
This is independent research that may proceed once the validator and benchmark conventions exist. It is a comparison point, not the presumed production architecture.
Gate B: Odd requests use the constructive path and benchmark results distinguish search, construction, validation and rendering.
Phase 2: replace the core search
Start with a clear scalar implementation. Demonstrate completeness and benchmark it before adding specialized data structures or SIMD.
Compare ascending, descending and justified best-fit order on the stable skyline implementation. Select the single-thread default from measured time-to-first-solution results.
Apply canonical positioning of the unique 1x1 square once placement/state semantics are stable.
Gate C: The skyline solver is independently validated, has a selected deterministic single-thread policy, and materially improves the baseline.
Phase 3: add pruning from cheapest to more expensive
Implement the proven constant/low-cost checks first and measure each independently.
Add the monotonic geometric feasibility check, measuring whether incremental maintenance is worthwhile.
Add gcd or bounded subset-sum component checks last because their per-node cost is potentially higher. Trigger them selectively.
Gate D: Retain a pruning rule by default only when it is sound and produces a measured net improvement on the benchmark set. Record prune counts as well as elapsed time.
Phase 4: parallelize the proven search
Parallelize only after the compact state, candidate policy and pruning rules are stable. Use over-decomposed tasks, dynamic scheduling and prompt first-solution cancellation.
Gate E: Thread-safety checks pass and scaling is reported for 1, 2, 4 and available hardware threads without regressing deterministic single-thread operation.
Phase 5: evaluate conditional experiments
Instrument duplicate-state frequency first. Keep memoization only if its hit rate and wall-time benefit justify memory and contention costs.
Treat this as an alternative/interim optimization for the old cell solver. Do not implement it automatically if #4 removes the cell grid and makes it redundant.
Completion criteria
Tracked issues
Phase 0 complete — Gate A passed
Implemented each issue sequentially on its own branch/worktree, with review before merge:
Results::set()assertion fix.Final verification on merged-equivalent
ddf07e7:Clean single-thread Apple arm64 Release baseline against exact framework commit
598667b:Order 9 is supported by the runner; its historical ~158.69 s result is retained rather than spending multiple minutes per repeated local baseline run.
Gate A is satisfied: Debug and applicable sanitizers pass, feasible solver output is independently validated, and a reproducible deterministic single-thread baseline exists. The roadmap remains open for Phase 1.
Phase 1 complete — Gate B passed
Implemented each issue sequentially on its own branch/worktree, with review before commit and merge:
3e667d6): odd ordersN >= 9now search only the even predecessor, geometrically translate its placements, and construct the enlarged border. Search and construction are explicit internal paths and separate benchmark fields. Order-9 search counters exactly match order 8.0a7ce1e): optional OR-Tools CP-SAT reference model withNoOverlap2D, exact fill, edge exclusions, equal-copy ordering, independent validation, repeat benchmarking, model/memory/worker reporting, and documented keep-as-reference / defer-DLX decisions. OR-Tools is not a native or default-test dependency.Verification:
Measured results:
Gate B is satisfied: applicable odd requests use the constructive route, and benchmarks separately report search, construction, independent validation, and rendering. The roadmap remains open for Phase 2.
Phase 2 complete — Gate C passed
Implemented each issue sequentially on its own branch/worktree, with independent review before commit and fast-forward merge:
d751d1b): replaced the board-area cell DFS with a scalar smallest-width-valley skyline, exact undo, public/direct benchmark routes, and independently validated ascending/descending coverage.74bde26): compared ascending, descending, and exact-width-first best-fit policies. Ascending remains the deterministic single-thread default; best-fit's slightly smaller tree was slower, descending was materially worse, and unsupported randomized/duplicate-work portfolios were deferred.f37e087): constrained the unique 1x1 square to a closed D4 fundamental triangle, with all eight transforms and even/odd boundary stabilizers covered. No repeated square copies are labeled.Final D4-enabled counted measurements on Apple arm64 Release, with independent validation and stable counters:
For comparison, the Gate A cell-DFS order-8 baseline was 1.817 s and 60,485,176 nodes. The final order-8 search is therefore about 7.4x faster with 95.2% fewer nodes on the recorded machine. D4 alone reduced the stable skyline tree by 62.1% for order 8 and 64.6% for direct order 9.
Verification on the final merged-equivalent tree:
10x10/11x11 decision: testing was explicitly evaluated in all three issues. Public order 10 with the final D4 skyline still exceeded a 45-second cap. Public order 11 performs exactly that order-10 predecessor search before cheap odd construction, so neither is suitable for routine CTest yet. They remain bounded opt-in heavyweight benchmarks. Direct order 11 is a distinct larger-core experiment and must not be reported as public order-11 performance.
Gate C is satisfied: the skyline solver is independently validated, ascending is the measured deterministic single-thread policy, D4 canonicalization is sound, and the implementation materially improves the recorded baseline. The roadmap remains open for Phase 3 pruning.
Phase 3 / Gate D is complete.
Completed sequentially:
e27427d): generalized valley-capacity pruning, covering width-one and width-two narrow gaps. Default-on after reducing median counted time by 10.3% (order 7) and 9.9% (order 8).220cec0): largest-remaining-square empty-box feasibility. Default-on after small public-path counter-free gains (0.12% order 7, 0.89% order 8); the 1.39% direct-order-9 regression and portability limitation are documented.39ff5cb): component detection plus gcd and bounded subset-sum feasibility, with boundary-event and periodic-eight schedules. Both modes remain opt-in/default-off: gcd slowed representative cases about 4.3%, subset sum 6.8-7.5%, and periodic checking was worse.Each issue used its own branch/worktree, received an issue-specific review, passed Debug and ASan+UBSan suites, recorded correctness arguments and focused exhaustive comparisons, committed with issue references, pushed, opened as a PR, and was fast-forward merged. The final suite has 14 tests. Gate D's default-retention rule is reflected in the production configuration, and rejected component experiments remain reproducible through benchmark modes and dedicated counters.