Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Constraints, Roles, Rules and Regions

Every constraint is a role + one or more regions + a rule:

  • A role says how the engine reads the rule’s outcome: Goal (must end Satisfied for the puzzle to be solved) or Forbidden (must never be Violated; Pending and Satisfied are both fine during play).
  • A list of regions says where the rule applies. Most rules are single-region (regions.len() == 1); a few — Clone for Quoits-style ring duplications, future cross-region equality constraints — bind multiple regions and treat them collectively. The constraint owns its regions (no separate region registry elsewhere on the puzzle), so the renderer iterates puzzle.constraints().iter().flat_map(|c| &c.regions) to find every paintable region — combined with Region.presentation (above), this collapses what was per-genre paint code into a single uniform pass.
  • A rule says what holds over those regions — drawn from the small shared vocabulary defined below.

A puzzle is solved iff every Goal constraint is Satisfied and no constraint is Violated.

There is no library-wide “every coord decided” rule baked into the solved check. Whether a genre needs that depends on what kind of puzzle it is, and the asymmetry is real:

  • Value-filling puzzles (Sudoku, Hidato, KenKen, Numberlink) are solved when every coord is decided to a specific value; they include a Goal + All + Decided constraint to enforce it.
  • Lighting / shading / loop puzzles (Akari, Slitherlink, Nurikabe, Heyawake) are solved when their structural goal holds; unmarked cells are fine, and Decided is omitted.

In Akari you can solve while leaving non-bulb cells unmarked because the goal is “every cell lit” (ExactCount(Bulb, 1) per LosCross), not “every cell decided.” In Sudoku the opposite is true: every cell must commit, and that requirement is itself a constraint, not a property of the engine.

A killer cage is Sum { target: 23, domain: 1..=9 } on a Set of cells. A Sudoku row is Distinct on a Row. A 3×3 box is Distinct on a Rect. A thermo is Increasing on a Path. Slitherlink’s loop is Path { mark: Binary(true), closed: true } on Union([AllOf(EdgesH), AllOf(EdgesV)]). A Quoits clone group is Clone over multiple Set-shape regions, one per ring — the only case in the current vocabulary where regions.len() > 1.

pub struct Constraint {
    pub role: Role,

    /// Owned regions the rule applies over. Length-1 for single-
    /// region rules (the common case); length-N for multi-region
    /// rules like `Clone`.
    pub regions: Vec<Region>,

    pub rule: Rule,
}

Constraints are identified by their slice index in puzzle.constraints() — that’s the propagator’s cache key, the violation report’s locator, the trace’s per-step constraint reference. There’s no separate id field because the slice index already does the job: stable within a puzzle (the list is built by Genre::build_constraints and rebuilt — in the same canonical order — on every mutation), O(1) to look up, no boilerplate at construction.

Constraint exposes shorthands for the two common cases:

impl Constraint {
    pub fn one(role: Role, region: Region, rule: Rule) -> Self;
    pub fn many(role: Role,
                regions: impl IntoIterator<Item = Region>,
                rule: Rule) -> Self;
    /// `Role::Goal` single-region — the common case.
    pub fn goal(region: Region, rule: Rule)      -> Self;
    /// `Role::Forbidden` single-region.
    pub fn forbidden(region: Region, rule: Rule) -> Self;
}

build_constraints implementations use goal / forbidden to keep the emission sites compact.

pub enum Role {
    /// Must be `Satisfied` for the puzzle to be solved. *Drives*
    /// the propagator toward solution: forced moves come from
    /// `Goal` constraints. Most rules are Goals — Sudoku
    /// `Distinct`, Akari per-cell `ExactCount(Bulb, 1)`, Killer
    /// `Sum`, Slitherlink loop `Path`.
    Goal,
    /// Must never be `Violated`, but doesn't drive solution. Used
    /// for **negative invariants** — pure validity gates the
    /// engine watches without trying to satisfy. The propagator
    /// treats `Violated` `Forbidden` constraints as
    /// `Status::Contradicted`, but doesn't emit forced moves from
    /// them.
    ///
    /// Examples that earn their `Forbidden` role:
    ///
    /// - Nurikabe **no-2×2** of shaded cells: a `NoTwoByTwo` rule
    ///   the puzzle must never violate, but no shaded cell is
    ///   *forced* by it.
    /// - Hashi **no-cross** between bridges: bridge edges may not
    ///   intersect, but the rule doesn't tell you which bridges to
    ///   draw.
    /// - Akari **at-most-one-bulb-per-LosCross**: paired with the
    ///   `Goal: AtLeastOne` half — the lower bound drives, the
    ///   upper bound gates.
    /// - Per-coord upper-bound caps in any genre.
    ///
    /// The `Forbidden` role is what lets these be expressed in the
    /// existing rule vocabulary without inventing new "negative"
    /// rule kinds. `NoTwoByTwo` is just a rule; it's the role that
    /// distinguishes "drive shading" from "watch for violations."
    Forbidden,
}

Regions

A region names a set of coords a constraint applies to, plus an optional render hint. Listing every coord by hand works but bloats the constraint list — a Sudoku row is nine cells, a 9×9 box is nine more, the entire grid has 27 such regions before any variants enter the picture. So RegionShape carries a small vocabulary of named shorthands; the engine expands each to its concrete coord list at evaluation time.

pub struct Region {
    /// What coords this region covers — the geometric vocabulary.
    pub shape: RegionShape,

    /// Optional render hint. `None` for purely structural regions
    /// (Sudoku rows / columns are solver-only — the row constraint
    /// fires `Distinct` but no row outline gets drawn). `Some(_)`
    /// for regions the renderer should depict — see the next
    /// chapter, *Decorations, Themes and Colors*, for what
    /// `RegionPresentation` carries.
    pub presentation: Option<RegionPresentation>,
}

pub enum RegionShape {
    /// Every coord across every layer the puzzle's `Substrate`
    /// populates. Reach for `AllOf(Layer)` instead unless you really
    /// mean every layer.
    All,
    /// Every coord of one specific layer. Slitherlink's loop is
    /// `Union([AllOf(EdgesH), AllOf(EdgesV)])`.
    AllOf(Layer),

    // Geometric, layer-parameterized: rows, columns, rects,
    // diagonals.
    Row { layer: Layer, r: usize },
    Col { layer: Layer, c: usize },
    Rect { layer: Layer, top: usize, left: usize,
           height: usize, width: usize },
    Diagonal { layer: Layer, from: Coord,
               dir: DiagDir, length: Option<usize> },

    // Cell-only LOS / adjacency. Take a `Coord` whose variant must
    // be `Coord::Cell` (validated at constraint construction);
    // `Los` walks until it hits a wall, `LosCross` is the union of
    // all four rays from a cell *including* the source.
    Los { from: Coord, dir: OrthoDir },
    LosCross { from: Coord },
    Neighbors4 { from: Coord },

    // Universal fallbacks — explicit Vec<Coord>, work over any
    // layer. The escape hatch for arbitrary cages, hand-authored
    // configurations, direction-sensitive rules.
    Set(Vec<Coord>),
    Path(Vec<Coord>),

    // Set algebra over shapes. "The row except this cell," etc.
    Union(Vec<RegionShape>),
    Intersect(Vec<RegionShape>),
    Diff(Box<RegionShape>, Box<RegionShape>),
}

pub enum OrthoDir { Up, Down, Left, Right }
pub enum DiagDir  { UpLeft, UpRight, DownLeft, DownRight }

Convenience builders sugar over the common cases:

impl Region {
    /// Bare region with no presentation — the common case for
    /// solver-only regions (Sudoku rows, Akari LosCross sets).
    pub fn shape(shape: RegionShape) -> Self {
        Self { shape, presentation: None }
    }

    pub fn all() -> Self;
    pub fn all_of(layer: Layer) -> Self;
    pub fn row(layer: Layer, r: usize) -> Self;
    pub fn col(layer: Layer, c: usize) -> Self;
    pub fn rect(layer: Layer, top: usize, left: usize, h: usize, w: usize) -> Self;
    pub fn cells_at(coords: impl IntoIterator<Item = Coord>) -> Self;
    /// Singleton-cell region — the common case for `Pin` constraints.
    pub fn single_cell(r: usize, c: usize) -> Self;
    pub fn los_cross(at: Coord) -> Self;
    pub fn neighbors4(from: Coord) -> Self;
    pub fn path(coords: Vec<Coord>) -> Self;
    pub fn union(parts: Vec<RegionShape>) -> Self;
    // ... one per RegionShape variant.
}

The with_presentation chain builder, plus the full set of construction examples, lives in the next chapter alongside the RegionPresentation definition.

Why Layer shows up twice. A RegionShape::Row { layer, r } declares which layer the row lives on; once the engine resolves that region to Vec<Coord>, every emitted Coord already carries the same information as its variant tag (Coord::Cell, Coord::EdgeV, …). The duplication is intentional: pre-resolution RegionShape values are symbolic — Row(3) alone would be ambiguous (cells? edges? corners?), so the Layer field disambiguates the symbolic form. Post-resolution, layer moves from explicit field to implicit variant tag. The cell-only shorthands (Los, LosCross, Neighbors4) skip the field because their semantics — wall-blocking, orthogonal adjacency — are only defined over cells; they take a Coord whose variant must be Coord::Cell, validated at constraint construction. Same currency (Coord) everywhere; one type for callers to remember.

Rules and violations

Each Rule variant is paired 1:1 with a Violation variant carrying the offending coords / counts. The mirroring is intentional: the engine pattern-matches violations to format prose, highlight cells, and grade without re-running the rule. Every rule has one discriminant; the engine’s dispatch key is just Rule, no sub-discriminants.

One file per rule. Each Rule variant owns its entire implementation in core/src/rules/<rule>.rs: tightness, mark-vocabulary requirement, structural validate, the slow-path consistency check, propagator-side combined eval+force-deduction, OR-tools CP-SAT encoding (gated behind #[cfg(feature = "ortools")] — used as a test oracle and bench baseline, not a production solver path), grader techniques, and (for rules with an incremental cache) the per-constraint aggregate’s build and apply/undo updates. Each file defines a marker ZST (e.g. pub struct ExactCount;) that impls crate::rules::RuleImpl.

The trait surface itself is intentionally small. Two methods do the actual work:

  • check(args, coords, game) -> ConstraintOutcome — required. Universal consistency check; reads candidate masks via Game, no aggregate access, no force-emission. Used by SimpleGame::status, generation validation, tests, and as the slow-path fallback inside the propagator. The CSP textbook’s check.
  • propagate(args, ci, prop, out) -> Option<ConstraintOutcome> — optional. Combined eval + force-emission for the AC-3 worklist. Reads the rule’s aggregate (if any), pushes implied moves into out. Returns Some(status) when the rule computed status, None to defer to the slow-path check. The Option<_> makes the asymmetry explicit: check is always definitive; propagate may shrug.

Plus the supporting methods (extract, tightness, mark_requirement, validate, techniques, build_aggregate), all defaulted except extract. Central dispatch sites (eval_rule in algorithm/eval.rs, the propagator’s propagate_at, and ortools::encode_constraint) are exhaustive matches that delegate to the rule’s trait method — adding a new variant is a compile error at every dispatch site, not a panic at runtime.

Propagator caches. Rules that maintain an incremental cache (ExactCount/AtMost/AtLeastOne/Pin/DegreeIn/ParityEven share a MarkAggregate; DistinctSequences and Path { closed: true } each have their own) plug into a single per-constraint Vec<AggregateState> on the propagator. AggregateState is a tagged union with variants None / Mark / DistinctSeq / PathClosed; the rule’s RuleImpl::build_aggregate produces the matching variant, and per-apply / per-undo updates dispatch through the rule module. CellMin is the exception: its storage is a shared SoA of counter state keyed by counter name (not by constraint), so it lives directly on the propagator with rule-side helpers in rules/cell_min.rs.

OR-tools is not on the prod path. The encode_ortools function each rule provides is for the test oracle (OrToolsSolver, used in core/src/tests/puzzles/* to cross-check FastSolver) and bench baselining. FastSolver is the production solver. Some Rule variants — Sum, Increasing, MinDifference, Polyomino, BoundedSize, ValueGroupedSize — currently have no FastSolver aggregate and return Pending from check; in production those rules are caught by trial-1 and slow-walk verification, not by an external CP-SAT call.

New puzzles get new rules by adding variants here, paired with the matching Violation variant. There is no escape hatch — if a puzzle needs a rule the vocabulary doesn’t cover, that’s a signal to extend the vocabulary, not work around it.

pub enum Rule {
    /// Marks in the region are pairwise distinct.
    /// Sudoku rows/cols/boxes, Hitori, Latin squares.
    Distinct,

    /// Marks in the region sum to `target`, each value drawn from
    /// `domain`. Killer cages, Arrow sums, Sandwich Sudoku.
    Sum { target: i64, domain: RangeInclusive<u8> },

    // ... Increasing, MinDifference, AtLeastOne, AtMost,
    // ExactCount — the rest of the counting / ordering family.

    /// The single coord in the region is committed to `mark`. The
    /// canonical shape of every clue-shaped given — Sudoku givens,
    /// Star Battle pre-placed stars, Hidato endpoints. Region must
    /// contain exactly one coord. Distinguished from
    /// `ExactCount { mark, n: 1 }` because the propagator can
    /// shortcut to "set candidates to {mark}" without going through
    /// the count machinery, and the grader treats `Pin` as "given"
    /// (which the renderer wants for distinguishing givens from
    /// deductions).
    Pin { mark: Mark },

    /// Count of `mark`-committed coords lies in `allowed`.
    /// Generalises `ExactCount`; covers Slitherlink/Masyu/Yajilin
    /// vertex degree `{0, 2}`. `allowed` must be sorted and deduped.
    DegreeIn { mark: Mark, allowed: AllowedCounts },

    // ─── Structural / shape rules ──────────────────────────────

    /// The coords marked `mark` form a single path under
    /// substrate-natural adjacency. `closed = true` for cycles;
    /// Slitherlink loop is `Path { mark: Binary(true), closed: true }`
    /// over edge coords with corner-sharing adjacency.
    Path { mark: Mark, closed: bool },

    // ... Connected, Polyomino, BoundedSize, NoTwoByTwo — the
    // other structural / shape rules.

    // ─── Completion + value-grouping ──────────────────────────

    /// Every coord in the region has its candidate set narrowed to
    /// a singleton — the *value* doesn't matter, only that the cell
    /// is committed. With `Goal` role, this is "every cell decided."
    /// Sudoku, Hidato, KenKen, Numberlink need it; Akari does not.
    Decided,

    // ... ValueGroupedSize — Fillomino's "components of value v have
    // size v."

    // ─── Per-cell + cross-rule shapes ──────────────────────────

    /// For every coord in the region, the named per-cell counter at
    /// that coord must be at least `min`. Counters are declared by
    /// the puzzle via `Puzzle::cell_counters`. The propagator forces
    /// the counter's target mark at the unique remaining contributor
    /// when only one is left in the coord's reach.
    CellMin { counter: String, min: u32 },

    // ... LoopFreezesCounts — cross-rule freeze for Slitherlink-style
    // "loop closed AND each clue's count satisfied."
}

/// Sorted, deduped list of allowed counts for `Rule::DegreeIn`.
/// Inline up to 4 entries — covers Slitherlink's `{0, 2}` and any
/// future genre that picks among a handful of values.
pub type AllowedCounts = SmallVec<[u8; 4]>;

pub enum Violation {
    /// `Distinct` violated: two coords share a mark.
    Distinct { a: Coord, b: Coord, mark: Mark },

    /// `Sum` exceeded its target.
    SumOver { target: i64, actual: i64 },
    /// `Sum`'s max possible total is below target.
    SumUnder { target: i64, max_possible: i64 },

    // ... ExactCountOver, ExactCountUnder, AtLeastOneStarved,
    // AtMostOver, OrderBroken, DegreeOutOfAllowed — the rest of
    // the counting / ordering violations.

    /// `Pin` violated: the pinned coord lost `mark` from its
    /// candidate set (the player or solver eliminated the pinned
    /// value, contradicting the given).
    PinLost { coord: Coord, mark: Mark },

    // ... Disconnected, PolyominoIsolated, BadPath, OverSize,
    // HasTwoByTwo — the structural-rule violations.

    /// `Decided` violated: a coord has no candidates left
    /// (irrecoverable empty domain).
    EmptyDomain { coord: Coord },

    // ... ValueGroupedSizeMismatch — completion / value-grouping
    // violations.
}

/// Discriminant-only mirror of `Rule`. Used by techniques to declare
/// which rule kinds they need present in `puzzle.constraints()` to be
/// applicable; the grader filters out techniques whose required
/// kinds don't appear, once per puzzle.
pub enum RuleKind {
    Distinct, Sum, Increasing, MinDifference,
    AtLeastOne, AtMost, ExactCount, Pin, DegreeIn,
    Connected, Polyomino, Path, BoundedSize, NoTwoByTwo,
    Decided, ValueGroupedSize,
    CellMin, LoopFreezesCounts,
}

impl Rule {
    pub fn kind(&self) -> RuleKind { /* trivial match */ }
}

Outcomes

What a constraint’s eval returns when the engine queries it, and the puzzle-wide rollup that follows from walking every constraint.

pub enum ConstraintOutcome {
    /// Every requirement of this constraint is met by current marks.
    Satisfied,
    /// Constraint isn't decidable yet — needs more state.
    Pending,
    /// Constraint can never be satisfied from this state.
    Violated(Violation),
}

pub enum Status {
    InProgress,
    Solved,
    /// The first constraint to evaluate as `Violated` in
    /// `puzzle.constraints()` order. The engine short-circuits on
    /// the first violation it finds — when several constraints are
    /// violated simultaneously, only one is reported, and "first"
    /// is the slice index of the constraint that produced it.
    /// Callers that want to enumerate every violation walk
    /// `puzzle.constraints()` themselves.
    Contradicted(Violation),
}

Move — the unit of change that narrows a candidate set, applied between eval rounds — lives in the Propagation engine chapter, where the moves-from-state derivation actually happens.

Givens are constraints, too

The constraint list is the puzzle’s every rule the solution must satisfy. Region rules (Sudoku row Distinct, Akari LosCross ExactCount(Bulb, 1)); invariants (Nurikabe NoTwoByTwo); shape rules (Path { closed: true } for the slitherlink loop); and the givens themselves. A sudoku given “cell (3, 4) = 7” is just Pin { mark: Numeric(7) } over a single-coord region. An akari clued wall translates to ExactCount over the wall’s visible floor cells (the wall position itself isn’t a coord, but its visibility region is). A killer cage is Sum over its cell set.

There is no separate “givens” surface on Puzzle — the constraint list is the canonical form. Genres still keep raw author-input fields (Akari.clues: HashMap<(r, c), u8>, Sudoku.clues: HashMap<(r, c), u8>) as editor scaffolding: the form a UI mutates when a player clicks “place a clue here.” But every such field is translated into constraints at construction (populate_ constraints); the constraint list is what every downstream consumer reads.

The Pin rule (see the Rules section above) is the workhorse for clue-shaped givens. Single-coord region, mark carries the pinned value. The propagator narrows the coord’s candidate set to {mark} immediately at game construction; a PinLost violation fires if the player or solver later eliminates that mark. Sudoku givens, Star Battle pre-placed stars, Hidato endpoints — all Pin.

Givens that aren’t Pin-shaped are still constraints, just under a different rule. Akari clue values are ExactCount over visible floors. Slitherlink cell clues are ExactCount over the cell’s four edges. Killer cage sums are Sum. Hashi island bridge counts are ExactCount over outgoing edges. Same story every time: the editor mutates raw fields, the constructor emits constraints, the engine reads constraints.

Mark / rule compatibility

Mark collapses to Binary | Numeric(u8), so compatibility is runtime-checked rather than gated by trait bounds. Sum, Increasing, and MinDifference are meaningful only over coords carrying Numeric marks; constructing one over a Binary region errors at constraint validation. Distinct, AtLeastOne, ExactCount, Pin, DegreeIn, and the structural rules (Connected, Polyomino, Path, BoundedSize, NoTwoByTwo) work for both mark variants.

Growing the vocabulary

When a new puzzle wants a rule the existing vocabulary doesn’t cover, the discipline is to extend the vocabulary, not work around it: add a variant on Rule, the paired variant on Violation, and a matcher in the engine. There is no escape hatch. Slitherlink’s “edges form a single closed loop” earned a slot via Path { mark: Binary(true), closed: true }; Masyu’s pearl rules will earn theirs the day Masyu lands.