Propagation engine

Underneath Solver, Generator, and Grader is a single propagation engine that runs the same way for every genre. It has one currency — Move — and two roles for the rule machinery, kept clean.

pub enum Move {
    /// Eliminate `mark` from `coord`'s candidate set.
    Eliminate { coord: Coord, mark: Mark },
    /// Narrow `coord`'s candidates to exactly `mark`.
    Commit    { coord: Coord, mark: Mark },
}

A Move is the unit of change. Eliminate is fine-grained (drop one mark from a coord’s candidate set); Commit is coarse (collapse to a singleton). Commit is conceptually equivalent to eliminating every other mark, but it’s its own variant because (a) it’s the player’s natural gesture — “place a bulb here” — and (b) the engine can shortcut it as a one-bit-set bitmask write instead of N eliminations. Game::apply and Game::undo both consume Moves.

The two roles, then:

• Constraints are predicates. They report Satisfied, Pending, or Violated(reason) against the current state. They don’t produce moves; the engine never asks them to.
• Propagator-tagged techniques produce moves. Techniques flagged Phase::Propagation are the cheap, rule-shape-specific propagators that emit Deduction { observed, moves }. Naked singles, bulb-clears-LOS, clue-saturation, etc. live here.

This split means a constraint’s eval is a yes/no/maybe check; the work of deriving what to do about it lives in propagators. If a propagator’s pass produces moves, those moves change the state, and the next pass evaluates constraints again. Fixed-point iteration handles correctness without Forces plumbing on the constraint side.

pub enum Phase {
    /// Cheap forward inference — runs in the inner propagation
    /// loop after every move, to fixpoint. Akari LOS clearing,
    /// Sudoku naked singles, clue-saturation,
    /// single-lighter-must-be-bulb.
    Propagation,
    /// Higher-cost pattern matching — runs in the outer grader
    /// loop only when propagation has stalled. X-Wing, Hidden
    /// Pairs, Akari clue-cover-by-elimination, paired-clue
    /// interactions.
    Pattern,
}

/// Object-safe: the grader holds a `Vec<Box<dyn Technique>>`.
pub trait Technique: Send + Sync {
    fn name(&self) -> &'static str;
    fn rule_kinds(&self) -> &'static [RuleKind];
    fn fire_once(&self, ci: usize, c: &Constraint, prop: &Propagator)
        -> Vec<TechniqueMatch> { /* default: empty */ }
    fn fire_all(&self, prop: &Propagator) -> Vec<TechniqueMatch>;
}

The loop

propagate(puzzle, game) -> Result<Vec<SolveStep>, Violation>:
    loop:
        before = game.move_count()
        for each Technique t with PHASE = Propagation, applicable to puzzle:
            run t.fire on builder; apply resulting Deduction; record steps
        for each Constraint c in puzzle.constraints():
            if c.eval(game) == Violated(v):
                return Err(v)
        if game.move_count() == before:
            return Ok(steps)   # fixpoint reached

Each pass: run all applicable propagators, applying any moves they produce; then check every constraint for a violation; loop until no move is made. Constraints are pure predicates; propagators are the move-producing engine.

How callers use this

Three callers weave propagate into their own outer loops, each adapting the engine to a different goal.

Solver fires the generic Propagator — the same set of forced-move derivations the engine knows about, batched and unnamed for speed. There’s no per-move trace; the solver just wants the answer. When propagation stalls without a solution or contradiction, the solver branches (MRV-ordered open coord, trial-1 with intra-sweep cascade) and recurses.

Grader fires the same forced-move logic, but as named Phase::Propagation techniques, one at a time, so each move lands in the trace tagged with the technique that derived it. The profile-driven scorer reads those tags to assign difficulty. When propagation stalls, the grader walks Phase::Pattern techniques in priority order, fires the first one that hits, and re-enters propagation. When no Pattern technique fires either, it escalates through backward fallbacks (clue-cover, trial-1, trial-2/N), each itself a Pattern-phase technique recorded in the trace. See the Grader chapter for the full layering.

Discovery loop runs propagation to the stall point, captures the state as a specimen (board layout, prior moves, the trial-search-forced move that no technique predicted), applies that move, and continues. The harness mines specimens that expose gaps in the technique library.

Three solvers, one contract

FastSolver’s body is: propagate to fixpoint → trial-1 sweep (MRV order, intra-sweep cascade) → if still in progress, branch on the first MRV-ordered open coord. The propagation step uses the generic Propagator, which derives forced moves from each rule kind’s cached aggregate state — no genre-specific code. This is the production solve path for every genre.

SimpleSolver is the deliberate brute-force baseline: HashMap<Coord, Vec<Mark>> candidates, no propagation, full DFS. Used for cross-checks on small puzzles and as the bench reference every faster impl beats badly.

The OR-Tools wrapper in algorithm/ortools/ translates each constraint into CP-SAT primitives and asks Google’s solver for solutions. It’s slower than FastSolver and not on the production path; its job is to be a totally independent oracle. When the three disagree on solve(p, k).len() or on the solution sets, the bug is on our side.