queens-generator

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.

Install

pip install queens-generator
# or, from a checkout:
pip install -e .

Usage

from speed_stars import generate_speed_stars_puzzle

puzzle = generate_speed_stars_puzzle(grid_size=6)

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.

Difficulty

The generator discards puzzles that are too trivial. The thresholds are profiled per grid size in speed_stars/generate.py:

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.

Tests

pip install -e .[dev]
python -m pytest tests/

License

MIT.