Generator and human-style solver for LinkedIn-Queens / Star Battle puzzles.
The package is named speed_stars (the original internal name) for backward compatibility with existing consumers; the project distribution is named queens-generator to match the player-facing brand.
This logic creates puzzles for Pemdas and validates community-submitted puzzles on Queens Puzzle Maker.
The generator refuses to ship any puzzle it can't solve without backtracking, using a hand-coded set of human deduction rules. When deduction stalls, instead of regenerating, it mutates the zone boundaries of the existing puzzle until deduction succeeds.
For the long-form write-up — why uniqueness isn't enough, how the deduction rules are ordered, why the generator refines instead of regenerates — see DESIGN.md.
pip install queens-generator
# or, from a checkout:
pip install -e .from speed_stars import generate_speed_stars_puzzle
puzzle = generate_speed_stars_puzzle(grid_size=6)The puzzle below is one such 6×6 board — play it here:
puzzle.zone_grid is a list-of-lists where each integer is a region ID:
[[1, 5, 5, 5, 5, 5],
[1, 1, 5, 5, 5, 5],
[4, 4, 4, 5, 2, 5],
[5, 5, 5, 5, 2, 3],
[5, 5, 0, 5, 2, 3],
[5, 0, 0, 3, 3, 3]]puzzle.star_positions is the unique solution — one star per row, column, and region:
[Position(x=0, y=0), Position(x=1, y=3), Position(x=2, y=1),
Position(x=3, y=4), Position(x=4, y=2), Position(x=5, y=5)]puzzle.deductions is the ordered sequence of human-style steps that solve the puzzle, each with a natural-language reason. The first few for the puzzle above:
Deduction(cells=[Position(2,3), Position(2,4), Position(2,5)],
state='crossedOut',
reason='row 3 can only have a star in {zone_4}')
Deduction(cells=[Position(0,4), Position(1,4), Position(5,4)],
state='crossedOut',
reason='column 5 can only have a star in {zone_2}')
Deduction(cells=[...8 cells...],
state='crossedOut',
reason='{zone_1}, {zone_5} must have stars in rows 1, 2')The deduction list is also what powers in-app hints: each Deduction is explainable to a player without revealing the solution. For the full step-by-step trace of how this puzzle is solved by the deduction engine — all twelve hints in order, as a player would see them — see docs/hints.md.
The generator discards puzzles that are too trivial. The thresholds are profiled per grid size in speed_stars/generate.py:
| grid size | min solve rounds | min cell deductions |
|---|---|---|
| 5 | 3 | 12 |
| 6 | 3 | 14 |
| 7 | 3 | 17 |
| 8 | 3 | 18 |
| 9 | 3 | 12 |
| 10–12 | 4 | 15 |
The thresholds count work done by the propagation solver (solve_speed_stars), which is what the generator uses to decide whether a puzzle is uniquely solvable without backtracking. The explainable Deduction list returned to the player is built by a separate pass (generate_deductions) that shares the same rules but reorders them by how easy they are for a human to spot.
- Rounds is how many passes the propagation solver makes through the grid before it stops finding new deductions. Each pass applies subset elimination then per-cell checks; below the threshold the puzzle falls open in a sweep or two and isn't interesting.
- Cell deductions counts the per-cell branches specifically — subset-elimination steps (N rows spanning N zones) are tracked separately and don't count, since they're easier for humans to spot. The threshold forces each puzzle to also demand the harder per-cell reasoning.
- Zone size: independent of grid size, every zone must have at least 3 cells (
MIN_ZONE_SIZE). Smaller zones produce one-step "only cell left" deductions that aren't interesting.
A puzzle that solves but fails any threshold is discarded; generation retries from scratch with a fresh zone layout. Zone-boundary refinement only runs to make unsolvable puzzles solvable, never to make easy puzzles harder.
The thresholds are exposed and overridable:
from speed_stars import generate_speed_stars_puzzle, RECOMMENDED_THRESHOLDS
# Use the profiled defaults
puzzle = generate_speed_stars_puzzle(grid_size=8)
# Override for a specific run (e.g., easier 8x8 for a tutorial pack)
puzzle = generate_speed_stars_puzzle(grid_size=8, min_rounds=2, min_deductions=10)Grid sizes outside the profiled range fall back to the nearest known size via get_default_thresholds.
pip install -e .[dev]
python -m pytest tests/MIT.