Most procedural-puzzle generators verify puzzles have exactly one valid solution. That's what I shipped first. But most of the puzzles were way too easy, and the rest were impossible for humans to solve without guess-and-backtrack. I needed puzzles a human could actually solve, but still felt challenging.
The fix came in two layers.
- Model human deduction explicitly.
- A ranked rule set: forced stars, subset elimination, cell-level hypotheticals, X-Wing. And applied in priority order, simplest first.
- If the ruleset can't solve the puzzle without more than 1 level of backtracking, refuse it.
- When the rules stall, don't regenerate the board.
- This was the actually interesting bit. The unsolvability is almost never global, it's usually a few cells we can't figure out.
- Instead of throwing the board out, mutate the partition: reassign one ambiguous cell to an adjacent region, re-solve, accept if the count of unresolved cells dropped. Repeat until the puzzle becomes uniquely solvable, or no improving repartition exists.
- Only accept repartitions that don't break continuity of each partition, or shrink regions too much. Without this, the regeneration will often result in puzzles with long thin snakes or single-cell regions that too easy to solve.
Side benefits that fall out of this:
- Hints are free
- The solver can simply give a human readable description of each step it took.
- Difficulty rating is mechanical
- Count rule applications by tier (forced stars + pigeonhole = easy, X-Wing = hard). No ML, no calibration drift.
- Refinement saves a lot of throwaway work
- A non-trivial fraction of boards that pure generate-and-test would discard get rescued by a few partition swaps.
Live: https://queenspuzzlemaker.com/
Code: https://github.com/gitars/queens-generator
Full write-up: https://github.com/gitars/queens-generator/blob/main/DESIGN.md
Step-by-step deduction walkthrough on the example puzzle: https://github.com/gitars/queens-generator/blob/main/docs/hints.md
u/Guilty-Fan-9386 — 23 days ago