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

solver: replace cell DFS with smallest-valley skyline search #4

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

Background

The current row-major first-empty DFS stores every board cell and writes every cell of a square on placement and undo. The occupied region has a skyline invariant: each column is filled contiguously from the starting edge.

Published perfect-packing work specifically applied a smallest-valley skyline algorithm to Partridge instances, reporting first solutions through orders 13 and 14 and much lower order-10 time than the current implementation.

Proposed work

  • Represent the partial board as a compact skyline/valley profile.
  • Select the narrowest valley as the next branching location.
  • Place fitting squares at the far-left edge of that valley.
  • Maintain valleys efficiently and support exact undo.
  • Preserve square multiplicities and first-solution early exit.
  • Initially benchmark a simple vector/list implementation before considering trees or SIMD.

Acceptance criteria

  • Search remains complete for square Partridge instances.
  • Returned placements pass an independent validator.
  • Node counts and elapsed times are recorded for orders 6, 7, 8 and 9.
  • Compare ascending and descending candidate-size order.
  • Document state and per-node complexity.

References

## Background The current row-major first-empty DFS stores every board cell and writes every cell of a square on placement and undo. The occupied region has a skyline invariant: each column is filled contiguously from the starting edge. Published perfect-packing work specifically applied a smallest-valley skyline algorithm to Partridge instances, reporting first solutions through orders 13 and 14 and much lower order-10 time than the current implementation. ## Proposed work - Represent the partial board as a compact skyline/valley profile. - Select the narrowest valley as the next branching location. - Place fitting squares at the far-left edge of that valley. - Maintain valleys efficiently and support exact undo. - Preserve square multiplicities and first-solution early exit. - Initially benchmark a simple vector/list implementation before considering trees or SIMD. ## Acceptance criteria - Search remains complete for square Partridge instances. - Returned placements pass an independent validator. - Node counts and elapsed times are recorded for orders 6, 7, 8 and 9. - Compare ascending and descending candidate-size order. - Document state and per-node complexity. ## References - https://www.or.uni-bonn.de/~hougardy/paper/PerfectRectanglePacking.pdf - https://github.com/lightln2/partridge-solver - `main.cc:130-219`
mcp commented 2026-07-30 17:55:13 +01:00
Author
Collaborator
Copy Link
Copy Source

Implementation/review rationale before merge:

  • Replace the cell grid with one filled height per column. Equal adjacent heights form conceptual bars; board edges are full-height sentinels.
  • Select the local valley with minimum width, then lower height and leftmost x for deterministic ties. Branch over every available square fitting the valley width/board height at its far-left edge, with exact skyline undo.
  • Completeness follows because the selected valley's bottom-left cell must be covered, and no covering square can cross a taller neighbour or extend beyond the equal-height run. The search retains multiplicities and first-solution exit.
  • Expose ascending/descending policy and public/direct benchmark routes so odd construction does not conceal direct core-search results.

Exploratory direct Release measurements (Apple Clang 21, arm64, -O3 -DNDEBUG, one run) independently validated all completions:

order ascending nodes descending nodes
6 0.040 s 659,598 0.039 s 659,598
7 3.103 s 43,604,507 3.071 s 43,604,507
8 0.585 s 7,735,369 0.941 s 12,186,125
9 direct 3.831 s 45,840,266 >15 s timeout unavailable

Ascending is the initial default; issue #12 will benchmark additional policies on this stable skyline implementation.

10x10/11x11 test decision: a direct ascending order-10 probe exceeded 20 seconds. Public order 10 is direct; public order 11 first performs that same order-10 search before construction. They are documented heavyweight benchmark cases, not routine CTest cases. Direct order 9 covers the core independently of odd construction, while route-boundary tests verify that order 11 selects construction.

Review and verification:

  • independent diff review found no correctness issue;
  • Release 10/10 passed (6.90 s);
  • Debug 10/10 passed (45.06 s);
  • AddressSanitizer 10/10 passed (12.89 s);
  • UndefinedBehaviorSanitizer 10/10 passed (108.46 s);
  • benchmark self-test and git diff --check passed.

References: issue #4 acceptance criteria and Hougardy's smallest-width valley definition/branching rule in A Scale Invariant Exact Algorithm for Dense Rectangle Packing Problems.

Implementation/review rationale before merge: - Replace the cell grid with one filled height per column. Equal adjacent heights form conceptual bars; board edges are full-height sentinels. - Select the local valley with minimum width, then lower height and leftmost x for deterministic ties. Branch over every available square fitting the valley width/board height at its far-left edge, with exact skyline undo. - Completeness follows because the selected valley's bottom-left cell must be covered, and no covering square can cross a taller neighbour or extend beyond the equal-height run. The search retains multiplicities and first-solution exit. - Expose ascending/descending policy and public/direct benchmark routes so odd construction does not conceal direct core-search results. Exploratory direct Release measurements (Apple Clang 21, arm64, -O3 -DNDEBUG, one run) independently validated all completions: | order | ascending | nodes | descending | nodes | | --- | ---: | ---: | ---: | ---: | | 6 | 0.040 s | 659,598 | 0.039 s | 659,598 | | 7 | 3.103 s | 43,604,507 | 3.071 s | 43,604,507 | | 8 | 0.585 s | 7,735,369 | 0.941 s | 12,186,125 | | 9 direct | 3.831 s | 45,840,266 | >15 s timeout | unavailable | Ascending is the initial default; issue #12 will benchmark additional policies on this stable skyline implementation. 10x10/11x11 test decision: a direct ascending order-10 probe exceeded 20 seconds. Public order 10 is direct; public order 11 first performs that same order-10 search before construction. They are documented heavyweight benchmark cases, not routine CTest cases. Direct order 9 covers the core independently of odd construction, while route-boundary tests verify that order 11 selects construction. Review and verification: - independent diff review found no correctness issue; - Release 10/10 passed (6.90 s); - Debug 10/10 passed (45.06 s); - AddressSanitizer 10/10 passed (12.89 s); - UndefinedBehaviorSanitizer 10/10 passed (108.46 s); - benchmark self-test and `git diff --check` passed. References: issue #4 acceptance criteria and Hougardy's smallest-width valley definition/branching rule in *A Scale Invariant Exact Algorithm for Dense Rectangle Packing Problems*.
mcp closed this issue 2026-07-30 17:57:02 +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#4