skip to content

When a constraint solver builds a support rota, what does propagation do to the variables' domains before each guess?

level: middleimportance: must knowfreq 55%

answer

  1. reason cheaply between guesses
  2. remove values nothing can support
  3. cascade to a fixpoint
  4. empty domain refutes this branch
  5. all singletons means solved without guessing

basics

~20 s

Propagation deletes, from each domain, values that no constraint can support given the choices already made, and repeats until nothing more can be removed. It prunes whole subtrees cheaply, and an emptied domain proves the current branch is dead.

solid answer

~50 s

Propagation is the cheap reasoning that runs between guesses. For each constraint the solver asks, value by value, whether a candidate still has any partner value left in the other variables' domains; unsupported values are deleted, and each deletion can trigger more, so it loops to a **fixpoint**. Three things can come out of that loop: some domain becomes empty - a wipeout, which proves the current partial assignment extends to no solution, so the solver backtracks; every domain is reduced to a single value, which is a solution found without guessing at all; or several domains still hold options, and only then does the solver pick a variable and guess. The payoff is that a deletion high in the tree removes an entire subtree, while a model checked only once everything is assigned must walk that subtree leaf by leaf.

code

pseudocode · 14 lines
pseudocode
function solve(vars):
    if propagate_to_fixpoint(vars) = WIPEOUT:
        return FAIL                       // some domain emptied: branch refuted
    if every domain in vars holds one value:
        return vars                       // solved without guessing

    v = variable with the smallest remaining domain
    for each value in domain(v):
        trial = copy(vars)
        set domain(v) in trial to { value }   // the guess
        result = solve(trial)
        if result is not FAIL:
            return result
    return FAIL                           // every value refuted: backtrack

go deeper

for a junior

Recall that a solver shrinks the candidate sets as it goes, instead of generating whole rosters and testing them. Knowing that much is enough at this stage.

for a middle

Explain the fixpoint loop and its three outcomes - wipeout, all-singletons, and a genuine choice point - and be able to trace one narrowing by hand on a two-day example.

for a senior

Show that you can tell a local refutation from global infeasibility when reading solver output, and that you tune propagation strength per constraint rather than globally.

for a principal

The trade you own is work per node against nodes visited, across a model the team will keep editing; a model that only performs under maximal consistency is fragile to the next rule change.

## Search alone is hopeless A quarter has about ninety days and a handful of eligible people per day. Enumerating assignments and checking the rules at the end is an astronomically large walk, and satisfiability of a finite-domain constraint model is NP-complete in general, so no solver escapes exponential worst cases. What a solver does instead is spend a little polynomial reasoning between guesses so that most of that space is never visited. ## What propagation actually does For each constraint, the solver looks at the domains of the variables it mentions and asks of each candidate value: **is there still any combination of values in the other domains that would satisfy this constraint?** A value with no such support cannot appear in any solution, so it is deleted. Deleting it may leave some value in a neighbouring domain unsupported, so the process cascades and is run to a **fixpoint** - the state where no constraint can remove anything more. Reasoning one constraint at a time to this level is called **arc consistency**. A worked narrowing, with Friday of week 3 already fixed to Ben: ```pseudocode saturday domain = { ana, ben, cleo } rule: no person on two consecutive days -> remove ben -> { ana, cleo } rule: cleo is unavailable that weekend -> remove cleo -> { ana } now saturday is fixed to ana, which cascades: sunday domain = { ana, dana } -> remove ana -> { dana } ``` Two days got decided and no guess was made. ## The loop 1. Propagate to a fixpoint. 2. If a domain is empty, the branch is refuted: undo the last guess and try the next value (**backtracking**). 3. If every domain holds one value, that assignment is a solution. 4. Otherwise choose a variable, guess one of its remaining values, and go to 1. Step 3 is the case candidates forget: a well-constrained model can be solved by propagation alone, with the search never branching. ## Wipeout is local, not global An empty domain proves that **the current partial assignment** extends to no solution. It does not prove the model is infeasible - only that this branch is. The model is infeasible when the search has refuted every branch, which is a much stronger and much more expensive statement. ## What it buys | | No propagation | Propagate before each guess | |---|---|---| | When a rule is consulted | Once every variable is assigned | After every change to any domain | | Cost of a dead branch | Walk it to the leaves | One fixpoint, then cut | | Effect of a rule that fixes a day | None until the end | Cascades into neighbouring days | | Cost per node | Near zero | Polynomial, and worth it | Propagation is not free - it runs after every domain change - but each removed value removes every branch beneath it, so the trade is almost always favourable. Solvers tune it by strength: cheap reasoning on every constraint, stronger reasoning on the few that pay for it. ## Strength varies with how a rule is written Two logically equivalent statements can propagate very differently. "These seven days take seven different people" stated as one group constraint lets the solver reason about the group as a whole - if four of the days have shrunk to the same four candidates, the fifth day can lose all four immediately. The same rule stated as twenty-one pairwise inequalities only ever removes a value once some day is actually fixed. Same solutions, weaker pruning. ## What interviewers listen for The things that separate a real answer here: - Naming the fixpoint, rather than describing a single pass. - Getting the direction right: propagation removes values that **cannot** participate, it does not choose values. - Reading a wipeout as a refutation of the branch, not of the model. - Knowing that propagation can finish the job, so "the solver always has to guess" is wrong. - Connecting propagation strength to how the constraint was written, which is the bridge to why re-modelling changes solve time.

  • Why not propagate as strongly as possible at every node?
    Stronger consistency prunes more but costs more per node, and the cost is paid at every node whether it helps or not. Solvers therefore run cheap reasoning on every constraint and reserve stronger reasoning for the few that repeatedly pay for themselves. It is the usual trade: work per node against nodes visited.
  • If propagation empties a domain, is the rota impossible?
    No - it proves only that the current partial assignment cannot be extended, so the solver undoes its last guess and tries another value. The rota is impossible only when every branch has been refuted, which the solver has to establish by exhausting the search space under its constraints.
  • Does the order in which constraints are propagated change the result?
    It changes the work, not the answer: the fixpoint of this kind of reasoning is the same set of domains whichever order the constraints are visited in. Ordering heuristics exist to reach that fixpoint with fewer passes, which matters because propagation runs at every node.

saying these in an interview costs you the question

  • Saying propagation assigns values rather than removing them
  • Treating an emptied domain as proof the whole model is infeasible
  • Believing the solver must guess before any domain can shrink
  • Claiming constraints are only checked once every variable is assigned
  • Assuming two logically equivalent rules always prune equally well