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

solver: prune states that cannot place remaining large squares #15

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

A partial state may leave the correct total empty area while making a remaining large square geometrically impossible to place. The current search does not test this directly.

A sound monotonic check for a remaining k square is whether the current empty region contains any k x k box. In a skyline representation this can be checked by finding a width-k window whose maximum height leaves at least k rows.

Proposed work

  • Detect when any remaining square size has no feasible empty k x k region.
  • Consider progressively stronger capacity bounds for multiple remaining copies.
  • Schedule the check adaptively or incrementally to control overhead.

Acceptance criteria

  • The basic single-square test has a documented soundness argument.
  • Tests include states with sufficient area but no feasible large-square placement.
  • Measure invocation count, prune count and net elapsed-time effect.
  • Stronger multiplicity bounds are added only with proof and measurement.
## Background A partial state may leave the correct total empty area while making a remaining large square geometrically impossible to place. The current search does not test this directly. A sound monotonic check for a remaining `k` square is whether the current empty region contains any `k x k` box. In a skyline representation this can be checked by finding a width-`k` window whose maximum height leaves at least `k` rows. ## Proposed work - Detect when any remaining square size has no feasible empty `k x k` region. - Consider progressively stronger capacity bounds for multiple remaining copies. - Schedule the check adaptively or incrementally to control overhead. ## Acceptance criteria - The basic single-square test has a documented soundness argument. - Tests include states with sufficient area but no feasible large-square placement. - Measure invocation count, prune count and net elapsed-time effect. - Stronger multiplicity bounds are added only with proof and measurement.
mcp commented 2026-07-31 08:25:13 +01:00
Author
Collaborator
Copy Link
Copy Source

Implemented the monotonic remaining-large-square feasibility check on codex/issue-15-large-square-pruning.

Soundness: a side-k square has a feasible empty skyline box only if at least k consecutive columns have filled heights no greater than board height - k. If the largest remaining square fits, every smaller remaining side geometrically fits within the same box, so only the largest size with non-zero multiplicity needs an O(board width) scan. Rejecting a state when that scan fails is a necessary, not heuristic, condition. No stronger multiplicity bound was added.

Focused tests cover a state with sufficient total empty area but no 2x2 box, a feasible box, largest-side monotonicity, isolated counters, and enabled/baseline exhaustive feasibility for orders 1-5. The benchmark supports all, valley-capacity, large-square, and none modes.

Counter-free Release measurements (Apple Clang 21.0.0, -O3 -DNDEBUG, D4 symmetry, one warm-up + seven repetitions; counters stable and all results independently validated), compared with valley-capacity alone:

  • Order 7 exhaustive: 0.947 s / 13,833,048 nodes baseline; 0.946 s / 13,221,239 nodes enabled (4.4% fewer nodes, 227,321 prunes, 0.12% median time improvement).
  • Order 8 first solution: 0.197 s / 2,724,096 nodes baseline; 0.195 s / 2,597,678 nodes enabled (4.6% fewer nodes, 38,177 prunes, 0.89% median time improvement).
  • Order 9 direct: 1.208 s / 14,995,127 nodes baseline; 1.225 s / 14,840,146 nodes enabled (1.0% fewer nodes but 1.39% median time regression).

Public order 9 constructs from the improving order-8 search, so the production benchmark set has a small net improvement and the rule remains default-on. The direct-order-9 regression is documented as a portability/policy limitation. Checking only every fourth placement depth was measured and rejected: it was slower than every-node checking by 2.2% (order 7), 2.3% (order 8), and 0.6% (direct order 9). Incremental per-size window state was not added because the current O(W) scan recovers its cost on the public set and no measurement justified the extra state/undo complexity.

Validation: Debug CTest 13/13, ASan+UBSan CTest 13/13, Release benchmark modes, benchmark self-test, warning-enabled syntax check, Python compile check, and git diff --check. Issue-specific review found no blocking or correctness findings; it noted that the small default-path timing margin may vary across platforms.

Implemented the monotonic remaining-large-square feasibility check on `codex/issue-15-large-square-pruning`. Soundness: a side-`k` square has a feasible empty skyline box only if at least `k` consecutive columns have filled heights no greater than `board height - k`. If the largest remaining square fits, every smaller remaining side geometrically fits within the same box, so only the largest size with non-zero multiplicity needs an `O(board width)` scan. Rejecting a state when that scan fails is a necessary, not heuristic, condition. No stronger multiplicity bound was added. Focused tests cover a state with sufficient total empty area but no 2x2 box, a feasible box, largest-side monotonicity, isolated counters, and enabled/baseline exhaustive feasibility for orders 1-5. The benchmark supports `all`, `valley-capacity`, `large-square`, and `none` modes. Counter-free Release measurements (Apple Clang 21.0.0, `-O3 -DNDEBUG`, D4 symmetry, one warm-up + seven repetitions; counters stable and all results independently validated), compared with valley-capacity alone: - Order 7 exhaustive: 0.947 s / 13,833,048 nodes baseline; 0.946 s / 13,221,239 nodes enabled (4.4% fewer nodes, 227,321 prunes, 0.12% median time improvement). - Order 8 first solution: 0.197 s / 2,724,096 nodes baseline; 0.195 s / 2,597,678 nodes enabled (4.6% fewer nodes, 38,177 prunes, 0.89% median time improvement). - Order 9 direct: 1.208 s / 14,995,127 nodes baseline; 1.225 s / 14,840,146 nodes enabled (1.0% fewer nodes but 1.39% median time regression). Public order 9 constructs from the improving order-8 search, so the production benchmark set has a small net improvement and the rule remains default-on. The direct-order-9 regression is documented as a portability/policy limitation. Checking only every fourth placement depth was measured and rejected: it was slower than every-node checking by 2.2% (order 7), 2.3% (order 8), and 0.6% (direct order 9). Incremental per-size window state was not added because the current `O(W)` scan recovers its cost on the public set and no measurement justified the extra state/undo complexity. Validation: Debug CTest 13/13, ASan+UBSan CTest 13/13, Release benchmark modes, benchmark self-test, warning-enabled syntax check, Python compile check, and `git diff --check`. Issue-specific review found no blocking or correctness findings; it noted that the small default-path timing margin may vary across platforms.
mcp closed this issue 2026-07-31 08:26:26 +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#15