grid: evaluate packed row-bit occupancy #2

New Issue

2026-07-30T16:23:33+01:00

mcp commented

2026-07-30 16:23:33 +01:00

Background

If the existing first-empty solver is retained as an interim or comparison implementation, its int_fast64_t cell grid causes O(k^2) stores for every placement and undo. For orders up to 10, each board row fits in one 64-bit word.

A packed-row representation can use row masks for placement/undo and bit scans for the next empty cell.

Proposed work

Prototype one or more uint64_t words per board row.
Use masks for square placement and clearing.
Use std::countr_zero or an equivalent operation for empty-cell discovery.
Keep support for boards wider than 64 cells.
Compare against the skyline redesign rather than assuming both are needed.

Acceptance criteria

Exact behavior matches the independently validated existing solver.
Record operation counts and timings for orders 6, 7 and 8.
Document whether this remains useful after skyline search lands.
Avoid merging it if it complicates or duplicates the selected skyline representation.

Reference

https://viddrobnic.com/writing/partridge/

## Background If the existing first-empty solver is retained as an interim or comparison implementation, its `int_fast64_t` cell grid causes `O(k^2)` stores for every placement and undo. For orders up to 10, each board row fits in one 64-bit word. A packed-row representation can use row masks for placement/undo and bit scans for the next empty cell. ## Proposed work - Prototype one or more `uint64_t` words per board row. - Use masks for square placement and clearing. - Use `std::countr_zero` or an equivalent operation for empty-cell discovery. - Keep support for boards wider than 64 cells. - Compare against the skyline redesign rather than assuming both are needed. ## Acceptance criteria - Exact behavior matches the independently validated existing solver. - Record operation counts and timings for orders 6, 7 and 8. - Document whether this remains useful after skyline search lands. - Avoid merging it if it complicates or duplicates the selected skyline representation. ## Reference - https://viddrobnic.com/writing/partridge/

mcp referenced this issue

2026-07-30 16:26:18 +01:00

roadmap: improve time to the first square solution #16

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: mgrettondann/partridge-cpp#2