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

solver: construct odd solutions from even predecessors #6

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

For even N, an order-N+1 solution can be constructed from an order-N solution without another exponential search. Let L = N(N+1)/2 and s = N+1; because L = (N/2)s, the enlarged L-shaped border can be tiled by exactly N+1 squares of side s.

This should make every odd request N >= 9 cost approximately the preceding even solve plus linear construction/output work.

Proposed work

  • Route odd N >= 9 requests through the N-1 solver.
  • Translate the predecessor placement into the enlarged board.
  • Add the N+1 new border squares in the two non-overlapping strips.
  • Preserve direct handling of trivial and unsatisfiable sizes.
  • Clearly separate constructed and searched solutions in internal APIs.

Acceptance criteria

  • Constructed solutions pass an independent full-board validator.
  • N=9 is derived from N=8 without entering the order-9 search.
  • Tests cover coordinates, multiplicities, bounds, overlap and complete coverage.
  • Benchmark the new N=9 path against the current recorded result.

References

## Background For even `N`, an order-`N+1` solution can be constructed from an order-`N` solution without another exponential search. Let `L = N(N+1)/2` and `s = N+1`; because `L = (N/2)s`, the enlarged L-shaped border can be tiled by exactly `N+1` squares of side `s`. This should make every odd request `N >= 9` cost approximately the preceding even solve plus linear construction/output work. ## Proposed work - Route odd `N >= 9` requests through the `N-1` solver. - Translate the predecessor placement into the enlarged board. - Add the `N+1` new border squares in the two non-overlapping strips. - Preserve direct handling of trivial and unsatisfiable sizes. - Clearly separate constructed and searched solutions in internal APIs. ## Acceptance criteria - Constructed solutions pass an independent full-board validator. - `N=9` is derived from `N=8` without entering the order-9 search. - Tests cover coordinates, multiplicities, bounds, overlap and complete coverage. - Benchmark the new `N=9` path against the current recorded result. ## References - https://oeis.org/A381976 - `main.cc` - `results.md`
mcp commented 2026-07-30 17:23:45 +01:00
Author
Collaborator
Copy Link
Copy Source

Implementation decision and review record:

  • Keep direct exhaustive search as an explicit internal API.
  • Route only odd orders N >= 9 through direct search of N-1, preserving direct handling for trivial and unsatisfiable smaller inputs.
  • Geometrically preserve predecessor (x, y) coordinates by re-encoding positions with the enlarged board stride, then tile the right and bottom strips with exactly N side-N squares.
  • Expose benchmark search and construction time separately. Instrumented order 9 must have exactly the order-8 search counters.

Review found and corrected the row-stride translation hazard before commit. Final review found no outstanding correctness or scope issues.

Verification:

  • Release CTest: 8/8 passed.
  • Debug CTest: 8/8 passed.
  • AddressSanitizer CTest: 8/8 passed.
  • UndefinedBehaviorSanitizer CTest: 8/8 passed.
  • git diff --check: clean.
  • Three-run interleaved benchmark: order-9 counter-free median 1.778 s search plus 0.458 us construction, versus the recorded 158.69 s direct-search result (about 89x faster); counted order-9 nodes are 60,485,176, exactly matching order 8.

The benchmark was necessarily recorded from the dirty issue worktree based on ddf07e7; environment and spread are documented in BENCHMARKING.md.

Implementation decision and review record: - Keep direct exhaustive search as an explicit internal API. - Route only odd orders `N >= 9` through direct search of `N-1`, preserving direct handling for trivial and unsatisfiable smaller inputs. - Geometrically preserve predecessor `(x, y)` coordinates by re-encoding positions with the enlarged board stride, then tile the right and bottom strips with exactly `N` side-`N` squares. - Expose benchmark search and construction time separately. Instrumented order 9 must have exactly the order-8 search counters. Review found and corrected the row-stride translation hazard before commit. Final review found no outstanding correctness or scope issues. Verification: - Release CTest: 8/8 passed. - Debug CTest: 8/8 passed. - AddressSanitizer CTest: 8/8 passed. - UndefinedBehaviorSanitizer CTest: 8/8 passed. - `git diff --check`: clean. - Three-run interleaved benchmark: order-9 counter-free median 1.778 s search plus 0.458 us construction, versus the recorded 158.69 s direct-search result (about 89x faster); counted order-9 nodes are 60,485,176, exactly matching order 8. The benchmark was necessarily recorded from the dirty issue worktree based on `ddf07e7`; environment and spread are documented in `BENCHMARKING.md`.
mcp closed this issue 2026-07-30 17:26:37 +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#6