solver: prune unplaceable large squares #27

2026-07-31T08:25:58+01:00

mcp commented

2026-07-31 08:25:58 +01:00

Summary

reject skyline states with no empty box for the largest remaining square
exploit size monotonicity to use one allocation-free linear scan per surviving node
add independent all, valley-capacity, large-square, and none benchmark modes and dedicated counters
document the proof, measurements, direct-order-9 limitation, and rejected periodic schedule

Measurements

Counter-free Release medians versus the valley-capacity baseline:

order 7 exhaustive: 0.947 s / 13,833,048 nodes baseline; 0.946 s / 13,221,239 nodes enabled
order 8 first solution: 0.197 s / 2,724,096 nodes baseline; 0.195 s / 2,597,678 nodes enabled
order 9 direct: 1.208 s / 14,995,127 nodes baseline; 1.225 s / 14,840,146 nodes enabled

The public benchmark set improves slightly because public order 9 constructs from order 8. The direct-order-9 regression and small portability margin are explicitly documented. An every-fourth-depth schedule was slower and was rejected.

Validation

Debug CTest: 13/13 passed
ASan+UBSan CTest: 13/13 passed
Release benchmark modes and self-test passed
warning-enabled syntax and Python compile checks passed
issue-specific review completed with no correctness or blocking findings

Closes #15

## Summary - reject skyline states with no empty box for the largest remaining square - exploit size monotonicity to use one allocation-free linear scan per surviving node - add independent `all`, `valley-capacity`, `large-square`, and `none` benchmark modes and dedicated counters - document the proof, measurements, direct-order-9 limitation, and rejected periodic schedule ## Measurements Counter-free Release medians versus the valley-capacity baseline: - order 7 exhaustive: 0.947 s / 13,833,048 nodes baseline; 0.946 s / 13,221,239 nodes enabled - order 8 first solution: 0.197 s / 2,724,096 nodes baseline; 0.195 s / 2,597,678 nodes enabled - order 9 direct: 1.208 s / 14,995,127 nodes baseline; 1.225 s / 14,840,146 nodes enabled The public benchmark set improves slightly because public order 9 constructs from order 8. The direct-order-9 regression and small portability margin are explicitly documented. An every-fourth-depth schedule was slower and was rejected. ## Validation - Debug CTest: 13/13 passed - ASan+UBSan CTest: 13/13 passed - Release benchmark modes and self-test passed - warning-enabled syntax and Python compile checks passed - issue-specific review completed with no correctness or blocking findings Closes #15

mcp added 1 commit 2026-07-31 08:26:00 +01:00

solver: prune unplaceable large squares 220cec06a9

A skyline may retain enough total empty area while no longer containing a box for its largest remaining square. Scan for the required consecutive low columns and reject such monotonic dead states.

Keep each pruning combination independently measurable and record the small public-path gain, the direct-order-9 regression, and the rejected periodic schedule.

Tests: Debug CTest (13 passed)

Tests: ASan+UBSan CTest (13 passed)

Refs: #15

mcp merged commit 220cec06a9 into main

2026-07-31 08:26:26 +01:00

mcp deleted branch codex/issue-15-large-square-pruning

2026-07-31 08:26:26 +01:00

mcp referenced this pull request

2026-07-31 08:41:34 +01:00

roadmap: improve time to the first square solution #16

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: mgrettondann/partridge-cpp#27