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

solver: add component-area feasibility pruning #13

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

Full-height columns or other completed boundaries can partition the remaining board into independent regions. Each such region must be fillable by a subset of the remaining square areas.

This necessary condition can reject states that pass total-area and local-fit checks.

Proposed work

  • Detect independently separated empty components in the chosen board representation.
  • Check component areas against remaining square areas and multiplicities.
  • Start with cheap gcd and bounded subset-sum tests.
  • Run expensive checks only when a partition is formed or another trigger indicates likely benefit.

Acceptance criteria

  • Component detection and area constraints have focused tests.
  • Pruning is proven necessary, not heuristic.
  • Compare incremental and periodic checking costs.
  • Record prune counts and net runtime effect on representative instances.
## Background Full-height columns or other completed boundaries can partition the remaining board into independent regions. Each such region must be fillable by a subset of the remaining square areas. This necessary condition can reject states that pass total-area and local-fit checks. ## Proposed work - Detect independently separated empty components in the chosen board representation. - Check component areas against remaining square areas and multiplicities. - Start with cheap gcd and bounded subset-sum tests. - Run expensive checks only when a partition is formed or another trigger indicates likely benefit. ## Acceptance criteria - Component detection and area constraints have focused tests. - Pruning is proven necessary, not heuristic. - Compare incremental and periodic checking costs. - Record prune counts and net runtime effect on representative instances.
mcp commented 2026-07-31 08:40:19 +01:00
Author
Collaborator
Copy Link
Copy Source

Implemented and measured component-area feasibility pruning on codex/issue-13-component-area.

Soundness: in the skyline every non-full column is empty through the top row, so adjacent non-full columns form one empty component and full-height columns are the only separators. Every remaining square must lie wholly within one component; therefore each component area must be a bounded subset sum of remaining square areas. Divisibility by the gcd of all remaining square areas is a cheaper necessary condition. The subset check tests each component against the shared reachable set; this can miss incompatible joint allocations but cannot reject a valid allocation.

Modes are independently selectable as none, gcd, and subset-sum. Checks are normally triggered only when a placement reaches full height and can change the component partition. An opt-in periodic-8 schedule supports the requested scheduling comparison. Focused tests cover component detection, gcd rejection, gcd-one/subset-sum rejection, a reachable partition, isolated counters, and boundary/periodic enabled-versus-baseline exhaustive feasibility for orders 1-5.

Counter-free Release measurements (Apple Clang 21.0.0, -O3 -DNDEBUG, existing cheap rules and D4 enabled, one warm-up + seven repetitions; all independently validated, stable counters):

  • Order 7: disabled 0.985 s / 13,221,239 nodes; gcd 1.027 s / 13,220,729 nodes (171,088 checks, 2,568 prunes); subset sum 1.052 s / 13,189,961 nodes (161,706 checks, 69,483 prunes).
  • Order 8: disabled 0.203 s / 2,597,678 nodes; gcd 0.212 s / 2,597,548 nodes (23,943 checks, 637 prunes); subset sum 0.219 s / 2,592,212 nodes (23,097 checks, 11,858 prunes).

Gcd slowed both orders by about 4.3% for fewer than 0.005% fewer nodes. Subset sum slowed order 7 by 6.8% and order 8 by 7.5% for 0.24% and 0.21% fewer nodes. In a three-repetition scheduling comparison, periodic-8 made 1,501,035/290,774 checks versus 161,706/23,097 boundary checks and slowed the disabled baseline by 10.5%/11.7%. Boundary-event checking is the cheaper schedule, but neither rule recovers its cost, so component pruning remains disabled by default per Gate D. The opt-in implementation and measurements prevent the experiment being reconsidered without new evidence.

Validation: Debug CTest 14/14, ASan+UBSan CTest 14/14, focused boundary and periodic tests, Release benchmark modes, runner self-test, warning-enabled syntax/Python compile checks, invalid CLI argument checks, and git diff --check. Issue-specific review found no findings. Limitation: performance was measured only on the documented AppleClang/macOS arm64 environment.

Implemented and measured component-area feasibility pruning on `codex/issue-13-component-area`. Soundness: in the skyline every non-full column is empty through the top row, so adjacent non-full columns form one empty component and full-height columns are the only separators. Every remaining square must lie wholly within one component; therefore each component area must be a bounded subset sum of remaining square areas. Divisibility by the gcd of all remaining square areas is a cheaper necessary condition. The subset check tests each component against the shared reachable set; this can miss incompatible joint allocations but cannot reject a valid allocation. Modes are independently selectable as `none`, `gcd`, and `subset-sum`. Checks are normally triggered only when a placement reaches full height and can change the component partition. An opt-in `periodic-8` schedule supports the requested scheduling comparison. Focused tests cover component detection, gcd rejection, gcd-one/subset-sum rejection, a reachable partition, isolated counters, and boundary/periodic enabled-versus-baseline exhaustive feasibility for orders 1-5. Counter-free Release measurements (Apple Clang 21.0.0, `-O3 -DNDEBUG`, existing cheap rules and D4 enabled, one warm-up + seven repetitions; all independently validated, stable counters): - Order 7: disabled 0.985 s / 13,221,239 nodes; gcd 1.027 s / 13,220,729 nodes (171,088 checks, 2,568 prunes); subset sum 1.052 s / 13,189,961 nodes (161,706 checks, 69,483 prunes). - Order 8: disabled 0.203 s / 2,597,678 nodes; gcd 0.212 s / 2,597,548 nodes (23,943 checks, 637 prunes); subset sum 0.219 s / 2,592,212 nodes (23,097 checks, 11,858 prunes). Gcd slowed both orders by about 4.3% for fewer than 0.005% fewer nodes. Subset sum slowed order 7 by 6.8% and order 8 by 7.5% for 0.24% and 0.21% fewer nodes. In a three-repetition scheduling comparison, periodic-8 made 1,501,035/290,774 checks versus 161,706/23,097 boundary checks and slowed the disabled baseline by 10.5%/11.7%. Boundary-event checking is the cheaper schedule, but neither rule recovers its cost, so component pruning remains disabled by default per Gate D. The opt-in implementation and measurements prevent the experiment being reconsidered without new evidence. Validation: Debug CTest 14/14, ASan+UBSan CTest 14/14, focused boundary and periodic tests, Release benchmark modes, runner self-test, warning-enabled syntax/Python compile checks, invalid CLI argument checks, and `git diff --check`. Issue-specific review found no findings. Limitation: performance was measured only on the documented AppleClang/macOS arm64 environment.
mcp closed this issue 2026-07-31 08:41:17 +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#13