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

bug: check completion before probing the next square #14

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

After placing a square, the solver calls largest_square(pos, n) before checking whether next_pos() returned grid.end():

pos = grid.next_pos(pos + idx);
idx = grid.largest_square(pos, n);
if (pos == grid.end()) { break; }

A completed order-8 run therefore probes beyond the grid. An out-of-tree AddressSanitizer build confirmed a heap-buffer overflow.

Proposed work

  • Check for completion immediately after next_pos().
  • Do not call largest_square() with the end sentinel.
  • Add a focused regression test that completes a board under AddressSanitizer.

Acceptance criteria

  • Order 8 completes without sanitizer findings.
  • Debug assertions remain enabled and pass.
  • A regression test would fail with the old ordering.
  • The fix is committed separately from performance changes.

Reference

  • main.cc:295-299
## Background After placing a square, the solver calls `largest_square(pos, n)` before checking whether `next_pos()` returned `grid.end()`: ```cpp pos = grid.next_pos(pos + idx); idx = grid.largest_square(pos, n); if (pos == grid.end()) { break; } ``` A completed order-8 run therefore probes beyond the grid. An out-of-tree AddressSanitizer build confirmed a heap-buffer overflow. ## Proposed work - Check for completion immediately after `next_pos()`. - Do not call `largest_square()` with the end sentinel. - Add a focused regression test that completes a board under AddressSanitizer. ## Acceptance criteria - Order 8 completes without sanitizer findings. - Debug assertions remain enabled and pass. - A regression test would fail with the old ordering. - The fix is committed separately from performance changes. ## Reference - `main.cc:295-299`
mcp commented 2026-07-30 16:50:29 +01:00
Author
Collaborator
Copy Link
Copy Source

Implemented on codex/issue-14-completion-check as two separate commits:

  • ccdcf03 adds a focused solver-completion regression for orders 1 and 8. Both results are checked by the independent validator for board dimensions, multiplicities, bounds, overlap, and complete coverage. Before the fix, the focused ASan run aborts on order 1 with a heap-buffer-overflow in find_solution().
  • ce39d0a moves the completion check immediately after next_pos() so the end sentinel is never passed to largest_square().

The minimal fix preserves solver behavior for non-terminal positions. Full CTest suites pass in Debug, Release, ASan, and UBSan configurations (5/5 each); the order-8 solver result is independently validated by the new regression.

Implemented on `codex/issue-14-completion-check` as two separate commits: - `ccdcf03` adds a focused `solver-completion` regression for orders 1 and 8. Both results are checked by the independent validator for board dimensions, multiplicities, bounds, overlap, and complete coverage. Before the fix, the focused ASan run aborts on order 1 with a heap-buffer-overflow in `find_solution()`. - `ce39d0a` moves the completion check immediately after `next_pos()` so the end sentinel is never passed to `largest_square()`. The minimal fix preserves solver behavior for non-terminal positions. Full CTest suites pass in Debug, Release, ASan, and UBSan configurations (5/5 each); the order-8 solver result is independently validated by the new regression.
mcp closed this issue 2026-07-30 16:54:09 +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#14