The generator
One puzzle for a sudoku-spec request. Generated from the docstrings by tools/gen_reference_md.py; public names only.
pencilmark.gen
Puzzle generator: one puzzle for a "sudoku-spec" request (Generator spec) -- difficulty / band / technique targets, classic and variants, any standard board size.
from pencilmark import generate # or pencilmark.gen.generate
r = generate({"format": "sudoku-spec", "format_version": 1, "board": {"rows": 9, "cols": 9}, "digits": 9,
"rules": [{"type": "box_grid", "origin": "r1c1", "box": [3, 3]}], "where": {"band": "Hard"}})
r["puzzle"] # sudoku-puzzle (with solution)
r["card"] # sudoku-grade card (difficulty, time, band, contains)
r["info"] # mode, givens, element counts, attempts, seconds, rejection reasons, unique_verified
The parts of the spec the generator runs are listed in Generator spec; anything else raises NotSupportedError. Every result is unique (re-checked with CP-SAT when OR-Tools is installed). Multi-grid boards are not supported by the generator.
pencilmark.gen.api
generate(spec) -> {"puzzle", "card", "info"}: the public entry point of pencilmark.gen.
| Name | What it does |
|---|---|
class Spec | what to generate. |
def board_of | the Board of a Spec: its size and layout, with the locked rules' all-different units (extra regions,… |
def feasibility | fast checks before any search; returns a list of problems (empty = go). |
def generate | generate one puzzle meeting a sudoku-spec request (Generator spec; a dict, JSON text or a… |
def is_unique | CP-SAT: does the puzzle JSON have exactly one solution? |
def uniquify | make a single-grid puzzle JSON unique by adding givens from its solution (the "solution" field, else the… |
class Spec
what to generate.
size board size (4, 6, 8, 9, 10, 12, 16; standard boxes)
layout None (one size x size grid) or a named multi-grid layout of 9 x 9 grids (samurai, ...)
locked sudoku-puzzle rules every result carries (all-different ones: diagonals, extra regions, windoku
windows, anti-knight, anti-king); the solution respects them
grid_givens [[min, max], ...] givens per grid of the layout (in its origins' order); None = no bound
quality None (no filtering), or the publishing checks as rate() takes them ({} = the defaults): a
candidate with a reject issue is not returned
elements {kind or class: N | [min, max] | "auto" | "full" | "min" | "partition"}: N = at least N needed elements
(0 / None / "auto" = allowed, not required); [min, max] = between min and max (max None = no cap;
[2, 2] = exactly 2). Classes count one colour / letter / parity of a kind: kropki_white, kropki_black,
x, v, odd, even ({"kropki_black": [2, 2], "kropki_white": "auto"}); {"kropki": "full"} = zero-given
full kropki (no dot = neither relation);
{"kropki": "min"} = zero-given minimal dot set; {"cage": "partition"} = killer tiled by cages, few
givens; {"cage": N} with max_givens=0 = killer with exactly N cages and no givens (CP-SAT);
"max" = as many as fit: the run uses its whole time and keeps the result with the most
shape {kind: {"length": [lo, hi], "sum": [lo, hi]}}: limits on the placed elements (length: cells of a
cage or line, the shaft of an arrow; sum: cages); None = no limit on that side
kinds shorthand: every listed kind keeps >= 1 needed element (each-kind mode)
target_band "Very Easy" .. "Extreme" (or 0..6): the card's band must equal it
target_difficulty [lo, hi] on the card's difficulty scale, or "max" / "min": the hardest / easiest result found in
the whole time
require technique codes the card must contain (e.g. ["XWG"]); strict_require = listed as the code itself,
not only as an alternative chip
symmetry None | rot180 | rot90 | mirror | mirror_v | diagonal | antidiagonal (for givens)
min_givens / max_givens digging floor / upper bound on the result's givens
max_elements upper bound on the number of rule elements
solver "logic" (every step solvable by human logic within the band cap: unique by construction) or
"cpsat" (uniqueness only; min kropki); cage-count and full kropki always use CP-SAT
seed, time_limit determinism and the overall budget in seconds
def from_any(cls, spec)
No docstring.
def board_of(s)
the Board of a Spec: its size and layout, with the locked rules' all-different units (extra regions, diagonals, windows; anti-knight / anti-king pairs), their other pair rules (nonconsecutive) and their puzzle JSON parts for every candidate
def feasibility(spec)
fast checks before any search; returns a list of problems (empty = go). Includes an information budget: givens and elements together must be able to carry log2(#grids) bits, and classic clue counts can't go below known minimums.
def generate(spec, log=None)
generate one puzzle meeting a sudoku-spec request (Generator spec; a dict, JSON text or a path). Returns {"puzzle": sudoku-puzzle (with solution; meta.generated_from = the spec's fingerprint), "card": sudoku-grade card, "info": {...}}. Raises NotSupportedError for a part of the spec the generator does not run, GenerationFailed when no puzzle met it in time.
def is_unique(puzzle, time_limit=30.0)
CP-SAT: does the puzzle JSON have exactly one solution? (None = undecided in time / unsupported rule).
def uniquify(puzzle, seed=0, time_limit=30.0, minimize=True)
make a single-grid puzzle JSON unique by adding givens from its solution (the "solution" field, else the first CP-SAT solution); any rule set CP-SAT can express. Each CP-SAT counterexample is cached; the cell the most cached counterexamples disagree on becomes the next given. With minimize, added givens that turn out unnecessary are dropped again. Returns a new puzzle JSON; raises GenerationFailed if there is no solution or CP-SAT can't decide.
pencilmark.gen.board
Standard n x n board geometry and random full grids.
| Name | What it does |
|---|---|
def grid_log2 | log2(number of n x n sudoku grids); a deliberately low estimate for sizes without a known count (safe for a… |
class Board | the cells, houses and neighbours of the board being generated: one n x n grid with standard boxes, or a… |
def grid_log2(n)
log2(number of n x n sudoku grids); a deliberately low estimate for sizes without a known count (safe for a budget bound: underestimating the entropy only lets more specs through).
class Board
the cells, houses and neighbours of the board being generated: one n x n grid with standard boxes, or a named multi-grid layout of 9 x 9 grids (samurai, super-samurai, ...: puzzle_json's layouts). Cell indices follow puzzle_json's cell order, so a puzzle's numbers string lines up. extra: more all-different units (extra regions, diagonals) that the solution must respect.
def rc(self, i)
No docstring.
def solution(self, rng, preset=None)
random full grid: bitmask backtracking, fewest candidates first. A board the backtracking cannot fill within its step budget (a layout with diagonals and windows) is completed by the engine's search from a few random digits, then relabelled with a random digit permutation. preset {cell: digit}: cells the grid keeps (then no relabelling); None if they cannot be completed.
def orbit(self, i, symmetry)
cells that must be given / empty together with cell i under the symmetry (None = just i).
pencilmark.gen.elements
src/pencilmark/gen/elements.py
Rule elements a generated puzzle can carry, true in a given solution grid.
An element is a tuple (kind, cells, extra): ("cage", sorted cells, total) killer cage, distinct digits ("thermo", path, None) strictly increasing from the bulb (path[0]) ("slow_thermo", path, None) non-decreasing from the bulb (path[0]) ("whisper", path, None) German whisper, neighbours differ by >= whisper_gap(n) ("renban", path, None) a set of consecutive digits, any order ("between", path, None) interior digits strictly between the two end circles ("entropic", path, None) every 3 consecutive cells: a low, a middle and a high digit (digit_third) ("modular", path, None) every 3 consecutive cells: three different remainders mod 3 ("parity_line", path, None) neighbours on the line alternate odd / even (the format's line kind parity) ("palindrome", path, None) reads the same from both ends (odd length, built from its centre) ("zipper", path, None) cells equally far from the centre sum to the centre digit (odd length) ("region_sum", path, None) the same sum in each box it passes through (two boxes or more) ("lockout", path, None) ends differ by >= lockout_gap(n), the other digits outside their range ("double_arrow", path, None) the two ends sum to the digits between them (5+ cells: shorter is a zipper) ("sandwich", row / column from the clue, total) digits between the 1 and the n sum to total ("xsum", row / column from the clue, total) the first X cells sum to total, X = the first digit ("skyscraper", row / column from the clue, count) cells higher than every earlier one ("little_killer", diagonal from the clue, total) the diagonal's digits sum to total (they may repeat) ("quadruple", (TL, TR, BL, BR), digits) the 2 x 2 block holds these digits (a corner circle) ("mathrax", (TL, TR, BL, BR), (op, value)) both diagonals combine to value by op (+ - x /), or op even / odd ("arrow", (circle,) + shaft, None) shaft digits sum to the circle digit ("kropki", (i, j), "white" | "black") consecutive / 1:2 ratio ("xv", (i, j), "X" | "V") sum 10 / sum 5 ("parity", (i,), 1 | 0) odd / even cell (graphical rule, not candidates)
| Name | What it does |
|---|---|
def norm_kind | a kind or an element class name -> its canonical name |
def base_kind | |
def element_class | the class of an element: its colour / letter / parity class where one exists, else its kind |
def in_class | |
def digit_third | the entropic group of digit v on an n-digit board (0 low, 1 middle, 2 high), as the engine splits them |
def lockout_gap | lockout: how far apart the ends must be (4 on 9 x 9, the format's default; about half the range otherwise) |
def line_holds | does a line of a kind checked as a whole (CENTRED, WHOLE) hold for these digits? |
def outside_value | the clue an outside element shows for its digits, read from the clue inwards |
def blocks | the 2 x 2 blocks (TL, TR, BL, BR) holding start |
def mathrax_clues | the mathrax clues true of a block's digits (TL, TR, BL, BR): both diagonals combine to the same value |
def corner_holds | |
def outside_lines | the lines through start an outside clue of kind reads, each from the clue inwards: the row and column… |
def whisper_gap | German-whisper gap: 5 on 9x9 (standard); about half the digit range otherwise. |
def ncomb | number of digit sets of size from 1..n summing to total (1 = the cage's digit set is fully determined). |
def length_of | an element's length as a template counts it: cells of a cage or line, the shaft of an arrow |
def fits | does the element meet its template's shape limits? |
def grow | elements of kind through cell start, disjoint from taken, true in the solution and within the… |
def planted_whisper | (path, {cell: digit}) of a German whisper of length cells to build a grid around: a random self-avoiding… |
def satisfies | does the full grid g satisfy the givens and every element? |
def to_json | puzzle JSON (pencilmark/puzzle_json format) for givens {cell: digit} and elements. |
def all_dots | every kropki dot true in the solution, and the dot-free pairs (for the full-kropki negative rule). |
def element_bits | upper bound (bits) on what one element of kind can tell: log2(placements) + log2(values). |
def norm_kind(k)
a kind or an element class name -> its canonical name
def base_kind(k)
No docstring.
def element_class(e)
the class of an element: its colour / letter / parity class where one exists, else its kind
def in_class(e, k)
No docstring.
def digit_third(v, n)
the entropic group of digit v on an n-digit board (0 low, 1 middle, 2 high), as the engine splits them
def lockout_gap(n)
lockout: how far apart the ends must be (4 on 9 x 9, the format's default; about half the range otherwise)
def line_holds(b, kind, cells, ds)
does a line of a kind checked as a whole (CENTRED, WHOLE) hold for these digits?
def outside_value(kind, ds)
the clue an outside element shows for its digits, read from the clue inwards
def blocks(b, start)
the 2 x 2 blocks (TL, TR, BL, BR) holding start
def mathrax_clues(ds)
the mathrax clues true of a block's digits (TL, TR, BL, BR): both diagonals combine to the same value
def corner_holds(kind, ds, x)
No docstring.
def outside_lines(b, kind, start)
the lines through start an outside clue of kind reads, each from the clue inwards: the row and column from both ends, or for a little killer the two diagonals from both ends (2 cells or more)
def whisper_gap(n)
German-whisper gap: 5 on 9x9 (standard); about half the digit range otherwise.
def ncomb(n, size, total)
number of digit sets of size from 1..n summing to total (1 = the cage's digit set is fully determined).
def length_of(e)
an element's length as a template counts it: cells of a cage or line, the shaft of an arrow
def fits(e, shape)
does the element meet its template's shape limits? shape {kind: {"length": (lo, hi), "sum": (lo, hi)}}
def grow(b, kind, sol, start, taken, rng, n=40, shape=None)
elements of kind through cell start, disjoint from taken, true in the solution and within the template's shape limits (fits); most informative first.
def planted_whisper(b, length, rng, tries=200)
(path, {cell: digit}) of a German whisper of length cells to build a grid around: a random self-avoiding path (fewest onward cells first) and digits alternating low / high, the gap kept, different within each house. Random grids rarely hold a whisper of more than about 20 cells (22 at most in 1,500 9 x 9 grids); a longer one is planted first and the grid completed around it. None if no path or digits were found.
def satisfies(b, g, givens, els)
does the full grid g satisfy the givens and every element? (cheap check used against cached alternative solutions; houses always hold because alternatives are valid grids of the same board).
def to_json(b, givens, els, sol=None, title=None)
puzzle JSON (pencilmark/puzzle_json format) for givens {cell: digit} and elements.
def all_dots(b, sol)
every kropki dot true in the solution, and the dot-free pairs (for the full-kropki negative rule).
def element_bits(b, kind)
upper bound (bits) on what one element of kind can tell: log2(placements) + log2(values). Loose on purpose: it only rejects specs that cannot possibly be unique.
pencilmark.gen.checks
Solvability / uniqueness checks used while generating.
Checker -- band-capped human solve (the engine with only techniques of band <= cap, or an explicit technique set): "solvable" means every cell is placed by logic, which implies a unique solution, so digging needs no separate uniqueness search. Oracle -- CP-SAT uniqueness with a counterexample cache (CEGAR): every alternative solution CP-SAT finds is kept and refutes later candidates in pure Python; only candidates that refute the whole cache reach CP-SAT.
| Name | What it does |
|---|---|
def params | the engine's params with search='human' (loaded once); path: a JSON params file of the same shape instead. |
def logic_techs | engine techniques usable by a human route (no computer search, no guessing, no note-taking pseudo moves). |
def band_techs | logic techniques of band cap or lower |
def code_techs | engine techniques whose chip is code (shape-split techniques included, e.g. |
class Checker | solvable by logic with techniques in allowed (default: band <= cap) -> unique by construction. |
class Oracle | CP-SAT uniqueness with a cache of alternative solutions (single worker: deterministic, light on the machine). |
def params(path=None)
the engine's params with search='human' (loaded once); path: a JSON params file of the same shape instead.
def logic_techs(P)
engine techniques usable by a human route (no computer search, no guessing, no note-taking pseudo moves).
def band_techs(P, cap)
logic techniques of band cap or lower
def code_techs(P, code)
engine techniques whose chip is code (shape-split techniques included, e.g. X-Wing for XWG).
class Checker
solvable by logic with techniques in allowed (default: band <= cap) -> unique by construction.
def left(self, givens, els)
cells the capped solve leaves unplaced (0 = solvable within the cap).
def ok(self, givens, els)
True if the capped solve places every empty cell
class Oracle
CP-SAT uniqueness with a cache of alternative solutions (single worker: deterministic, light on the machine).
def unique(self, givens, els)
True if CP-SAT proves the candidate (givens, els) has one solution; a cached alternative or a timeout is not unique
def refuted(self, givens, els)
True if a cached alternative still satisfies the candidate (it cannot be unique).
pencilmark.gen.search
Search procedures.
All functions take a Board, a random.Random and return (solution, givens {cell: digit}, elements) or None.
| Name | What it does |
|---|---|
def dig | givens-digging with elements added on demand. |
def partition | killer covering the board: keep n_givens random givens, tile the other cells with 2-cell informative… |
def cage_count | killer with EXACTLY n_cages cages and no givens: tile with 2-cell cages, then merge neighbouring cages… |
def full_kropki | zero-given full kropki (every consecutive pair has a white dot, every 1:2 pair a black one, no dot =… |
def min_kropki | zero-given kropki without the negative rule: all true dots, then remove dots while the puzzle stays unique… |
def pull | approach the band boundary from above: start from a puzzle the lower-band solve (low) can't finish (e.g. |
def dig(b, kinds, rng, chk, sol=None, min_givens=0, grid_floors=None, seeds=None, max_els=10 ** 6, symmetry=None, fixed=None, blocked=(), pool_tries=25, caps=None, dense=(), shape=None, most=(), deadline=None, keep=False)
givens-digging with elements added on demand.
seeds{kind: count} elements are placed first (apart from elements of their own kind), then themostclasses are packed; their cells, then their peers, are emptied first, so they tend to end up required; 2. the remaining givens are removed in random order (whole symmetry orbits at a time) down tomin_givens; when a removal breaks solvability (chk: band-capped logic), the most informative element ofkindsthrough that cell that restores it is added (if any), else the givens stay; 3. prune: every element the puzzle stays solvable without is dropped (no decorative elements). fixed {cell: True (stays given) / False (stays empty)}; blocked cells take no elements. kinds / seeds may name element classes (kropki_black, x, odd, ...); caps {class: max} limits how many of a class are added. dense: 2-cell / 1-cell classes seeded with EVERY instance true in the solution before digging (few-givens targets); pruning then removes the ones the puzzle doesn't need. shape {kind: limits}: the templates' length / sum limits (elements.fits). most: classes packed into the grid after the seeds, as many disjoint ones as a few random packings find, and never pruned. grid_floors [(cells, n)]: no grid of a layout goes below n givens. deadline (time.time()): when it passes, the attempt is given up (None), or with keep the digging stops and the givens still in place stay.
def partition(b, rng, chk, n_givens=0, min_els=0, cover=True)
killer covering the board: keep n_givens random givens, tile the other cells with 2-cell informative cages, then merge neighbouring cages (distinct digits, <= 6 cells) -- or delete cages if cover=False -- while the puzzle stays solvable within the checker's cap. A cell left alone becomes a given (a 1-cell cage is a given in disguise) when there are givens; with none it joins a neighbouring cage.
def cage_count(b, n_cages, rng, time_limit=30.0, deadline=None, log=None)
killer with EXACTLY n_cages cages and no givens: tile with 2-cell cages, then merge neighbouring cages (distinct digits) in batches while the puzzle stays UNIQUE (CP-SAT oracle with a counterexample cache; a failed batch is bisected). No human-solvability cap: the card grades whatever results.
def full_kropki(b, rng, time_limit=20.0)
zero-given full kropki (every consecutive pair has a white dot, every 1:2 pair a black one, no dot = neither): the grid fixes the whole puzzle, so draw grids until the dot set is unique.
def min_kropki(b, rng, time_limit=20.0, chk=None)
zero-given kropki without the negative rule: all true dots, then remove dots while the puzzle stays unique (CP-SAT oracle; with chk, while it stays solvable within the checker's cap) -> a minimal dot set.
def pull(b, sol, givens, els, chk, low, rng, symmetry=None, max_givens=None)
approach the band boundary from above: start from a puzzle the lower-band solve (low) can't finish (e.g. dug with every technique allowed), then put givens back (random order, whole symmetry orbits), skipping any that would let low finish, until the capped solve (chk) finishes. The result needs the cap's techniques (by the engine) and solves within the cap. Elements that became unnecessary are dropped. Returns (givens, els) or None.