mgrettondann/partridge-cpp
1
0
Fork 0
Code Issues 4 Pull Requests Activity

solver: add cheap valley and narrow-gap pruning #10

New Issue
Closed
opened 2026-07-30 16:23:34 +01:00 by mcp · 1 comment
mcp commented 2026-07-30 16:23:34 +01:00
Collaborator
Copy Link
Copy Source

Background

Most runtime is spent undoing failed placements. Temporary instrumentation counted about 60.5 million attempted placements and 60.5 million backtracks for order 8.

The smallest-valley literature obtains much of its speed from cheap necessary conditions, including checking whether remaining pieces that fit a valley have enough total area. Existing Partridge solvers also reject newly created width-one gaps and apply specialized width-two capacity checks.

Proposed work

  • Reject a valley when the total remaining area of fitting squares is below its area.
  • Add sound width-one gap rejection.
  • Generalize narrow-gap capacity checks where the proof is straightforward.
  • Keep each check inexpensive and separately switchable for measurement.

Acceptance criteria

  • Each rule has a documented correctness argument and focused tests.
  • No valid solution is removed in exhaustive small-instance comparisons.
  • Report nodes, checks, prune counts and elapsed time with each rule enabled independently and together.
  • Retain only rules whose measured benefit justifies their cost.

References

## Background Most runtime is spent undoing failed placements. Temporary instrumentation counted about 60.5 million attempted placements and 60.5 million backtracks for order 8. The smallest-valley literature obtains much of its speed from cheap necessary conditions, including checking whether remaining pieces that fit a valley have enough total area. Existing Partridge solvers also reject newly created width-one gaps and apply specialized width-two capacity checks. ## Proposed work - Reject a valley when the total remaining area of fitting squares is below its area. - Add sound width-one gap rejection. - Generalize narrow-gap capacity checks where the proof is straightforward. - Keep each check inexpensive and separately switchable for measurement. ## Acceptance criteria - Each rule has a documented correctness argument and focused tests. - No valid solution is removed in exhaustive small-instance comparisons. - Report nodes, checks, prune counts and elapsed time with each rule enabled independently and together. - Retain only rules whose measured benefit justifies their cost. ## References - https://www.or.uni-bonn.de/~hougardy/paper/PerfectRectanglePacking.pdf - https://github.com/lightln2/partridge-solver/blob/main/solver.h
mcp commented 2026-07-31 08:11:12 +01:00
Author
Collaborator
Copy Link
Copy Source

Implemented the Phase 3 valley-capacity rule on codex/issue-10-valley-pruning.

Soundness: until a selected valley reaches the lower of its neighbouring skyline heights (with board edges treated as full height), no square wider than that valley can occupy cells below the rim. Therefore the total area of all remaining squares no wider than the valley must be at least valley width * depth below rim. Rejecting a state when this necessary bound fails is sound and subsumes width-one and width-two capacity checks.

The rule is compile-time disabled in the benchmark's --no-pruning comparison mode and has dedicated check/prune counters. Focused tests cover width-one, width-two, general valley capacity, instrumentation, and enabled/disabled exhaustive feasibility for orders 1-5.

Release measurements (Apple Clang 21.0.0, -O3 -DNDEBUG, ascending policy, D4 symmetry, 1 warm-up + 5 repetitions; all independently validated, stable counters):

  • Order 7 exhaustive: 1.110 s / 14,997,603 nodes disabled; 0.996 s / 13,833,048 nodes enabled (10.3% time reduction, 7.8% node reduction; 7,411,551 valley prunes).
  • Order 8 first solution: 0.228 s / 2,931,203 nodes disabled; 0.205 s / 2,724,096 nodes enabled (9.9% time reduction, 7.1% node reduction; 1,606,836 valley prunes).

The measured net benefit justifies enabling the rule by default. Validation completed: Debug CTest 12/12, ASan+UBSan CTest 12/12, Release benchmark build and format checks, warning-enabled syntax check, and git diff --check. Review found one stale benchmark-documentation statement, which was corrected; no correctness findings remain.

Implemented the Phase 3 valley-capacity rule on `codex/issue-10-valley-pruning`. Soundness: until a selected valley reaches the lower of its neighbouring skyline heights (with board edges treated as full height), no square wider than that valley can occupy cells below the rim. Therefore the total area of all remaining squares no wider than the valley must be at least `valley width * depth below rim`. Rejecting a state when this necessary bound fails is sound and subsumes width-one and width-two capacity checks. The rule is compile-time disabled in the benchmark's `--no-pruning` comparison mode and has dedicated check/prune counters. Focused tests cover width-one, width-two, general valley capacity, instrumentation, and enabled/disabled exhaustive feasibility for orders 1-5. Release measurements (Apple Clang 21.0.0, `-O3 -DNDEBUG`, ascending policy, D4 symmetry, 1 warm-up + 5 repetitions; all independently validated, stable counters): - Order 7 exhaustive: 1.110 s / 14,997,603 nodes disabled; 0.996 s / 13,833,048 nodes enabled (10.3% time reduction, 7.8% node reduction; 7,411,551 valley prunes). - Order 8 first solution: 0.228 s / 2,931,203 nodes disabled; 0.205 s / 2,724,096 nodes enabled (9.9% time reduction, 7.1% node reduction; 1,606,836 valley prunes). The measured net benefit justifies enabling the rule by default. Validation completed: Debug CTest 12/12, ASan+UBSan CTest 12/12, Release benchmark build and format checks, warning-enabled syntax check, and `git diff --check`. Review found one stale benchmark-documentation statement, which was corrected; no correctness findings remain.
mcp closed this issue 2026-07-31 08:12:07 +01:00
Sign in to join this conversation.
No Branch/Tag Specified
Branches Tags
Labels
No items
No labels
Milestone
No items
No Milestone
Assignees
Clear assignees
mcp mgrettondann (Matthew Gretton-Dann)
No Assignees
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: mgrettondann/partridge-cpp#10