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

solver: break board dihedral symmetry #3

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

Square-board solutions have eight rotational/reflection symmetries. Because only one solution is required, the search can choose a canonical representative.

The unique 1x1 square is a convenient distinguished piece: any solution can be transformed so that its position lies in one canonical octant, with careful handling of axes and diagonals.

Proposed work

  • Define a canonical region for the unique 1x1 square.
  • Prune partial states once the 1x1 position makes the canonical condition decidable.
  • Verify boundary and diagonal cases.
  • Compare with cheaper/later corner-size canonicalization if useful.

Acceptance criteria

  • The symmetry constraint preserves at least one representative of every D4 orbit.
  • Tests cover all rotations/reflections and midline/diagonal cases.
  • Measure node and elapsed-time reduction.
  • Do not introduce labeled-copy symmetry.

References

## Background Square-board solutions have eight rotational/reflection symmetries. Because only one solution is required, the search can choose a canonical representative. The unique 1x1 square is a convenient distinguished piece: any solution can be transformed so that its position lies in one canonical octant, with careful handling of axes and diagonals. ## Proposed work - Define a canonical region for the unique 1x1 square. - Prune partial states once the 1x1 position makes the canonical condition decidable. - Verify boundary and diagonal cases. - Compare with cheaper/later corner-size canonicalization if useful. ## Acceptance criteria - The symmetry constraint preserves at least one representative of every D4 orbit. - Tests cover all rotations/reflections and midline/diagonal cases. - Measure node and elapsed-time reduction. - Do not introduce labeled-copy symmetry. ## References - https://www.or.uni-bonn.de/~hougardy/paper/PerfectRectanglePacking.pdf - https://github.com/lightln2/partridge-solver
mcp commented 2026-07-30 18:18:39 +01:00
Author
Collaborator
Copy Link
Copy Source

Implementation/review rationale before merge:

  • Use the unique 1x1 square to choose one D4 board orientation. For board width W, retain unit-square cells in the closed fundamental triangle x <= y <= floor((W - 1) / 2).
  • Every cell orbit maps into that triangle by reflecting toward an edge and swapping coordinates; closed diagonal/midline boundaries retain smaller stabilizer orbits on even and odd boards.
  • Apply the check only when side 1 is about to be placed, so the position is decidable. Larger repeated squares remain unlabeled and unconstrained.
  • Keep a compile-time D4-on production path and a D4-off benchmark path; instrument examined/rejected unit placements as prune checks/hits.

Sequential single-worker Release measurements (Apple Clang 21, arm64, -O3 -DNDEBUG, one warm-up and five runs), with stable counters and independently valid outputs:

route D4 counted median (range) nodes prune hits
order 8 public on 0.245 s (0.244–0.248) 2,931,203 1,329,567
order 8 public off 0.679 s (0.659–0.709) 7,735,369 0
order 9 direct on 1.705 s (1.671–1.740) 16,231,918 6,755,171
order 9 direct off 4.542 s (4.482–4.662) 45,840,266 0

D4 symmetry reduces nodes by 62.1% for order 8 and 64.6% for direct order 9; median solve time falls by 63.9% and 62.5% respectively.

10x10/11x11 decision: public order 10 with D4 and ascending policy still exceeded a 45-second cap. Public order 11 performs that exact order-10 predecessor search before cheap construction, so neither belongs in routine CTest yet. Both remain bounded heavyweight benchmark targets. Direct order 11 bypasses construction and is a distinct larger-core experiment, not public order-11 performance.

Review and verification:

  • focused tests cover all eight transforms, a distinct generic orbit, even/odd midlines, diagonals, corners, and the odd-board centre;
  • symmetry-enabled and disabled order-8 solutions pass independent validation;
  • Release, AddressSanitizer, and UndefinedBehaviorSanitizer CTest: 11/11 passed in each configuration;
  • independent Debug CTest: 11/11 passed (37.04 s);
  • benchmark self-test, Python byte-compilation, and git diff --check passed;
  • independent diff review found no correctness issue.

References: issue #3 acceptance criteria and Hougardy's D4 symmetry rule recommending the unique smallest square.

Implementation/review rationale before merge: - Use the unique 1x1 square to choose one D4 board orientation. For board width W, retain unit-square cells in the closed fundamental triangle `x <= y <= floor((W - 1) / 2)`. - Every cell orbit maps into that triangle by reflecting toward an edge and swapping coordinates; closed diagonal/midline boundaries retain smaller stabilizer orbits on even and odd boards. - Apply the check only when side 1 is about to be placed, so the position is decidable. Larger repeated squares remain unlabeled and unconstrained. - Keep a compile-time D4-on production path and a D4-off benchmark path; instrument examined/rejected unit placements as prune checks/hits. Sequential single-worker Release measurements (Apple Clang 21, arm64, -O3 -DNDEBUG, one warm-up and five runs), with stable counters and independently valid outputs: | route | D4 | counted median (range) | nodes | prune hits | | --- | --- | ---: | ---: | ---: | | order 8 public | on | 0.245 s (0.244–0.248) | 2,931,203 | 1,329,567 | | order 8 public | off | 0.679 s (0.659–0.709) | 7,735,369 | 0 | | order 9 direct | on | 1.705 s (1.671–1.740) | 16,231,918 | 6,755,171 | | order 9 direct | off | 4.542 s (4.482–4.662) | 45,840,266 | 0 | D4 symmetry reduces nodes by 62.1% for order 8 and 64.6% for direct order 9; median solve time falls by 63.9% and 62.5% respectively. 10x10/11x11 decision: public order 10 with D4 and ascending policy still exceeded a 45-second cap. Public order 11 performs that exact order-10 predecessor search before cheap construction, so neither belongs in routine CTest yet. Both remain bounded heavyweight benchmark targets. Direct order 11 bypasses construction and is a distinct larger-core experiment, not public order-11 performance. Review and verification: - focused tests cover all eight transforms, a distinct generic orbit, even/odd midlines, diagonals, corners, and the odd-board centre; - symmetry-enabled and disabled order-8 solutions pass independent validation; - Release, AddressSanitizer, and UndefinedBehaviorSanitizer CTest: 11/11 passed in each configuration; - independent Debug CTest: 11/11 passed (37.04 s); - benchmark self-test, Python byte-compilation, and `git diff --check` passed; - independent diff review found no correctness issue. References: issue #3 acceptance criteria and Hougardy's D4 symmetry rule recommending the unique smallest square.
mcp closed this issue 2026-07-30 18:19:14 +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#3