Constraint propagation repeatedly removes impossible values from variable domains and rechecks connected constraints until no further supported reduction appears. Propagation is an algorithmic and solving method, not a rule of any particular puzzle. Chess Programming Wiki covers related search ideas in game programs; Pagat covers games in its own collection, not general constraint-satisfaction theory.
Who this is for: Puzzle solvers who understand individual clues but want a systematic way to carry each consequence through the model.
- For constraint propagation, separate binding rules from practical principles, software conventions, and optional training methods before making a decision.
- Initialize domains, apply direct clues, enqueue affected constraints, and process them until the queue is empty. If a domain becomes empty, locate the assumption or earlier deduction causing contradiction. If several values remain, propagation has reached a fixed point rather than failed. Record the position, information, or assumptions so the reasoning can be checked instead of reconstructed from memory.
- Basic propagation does not solve every valid puzzle, and a fixed point does not establish that every remaining value participates in a complete solution. Stronger consistency or search costs more work. No method here promises a puzzle success rate or completion time. Treat every numeric score, resource count, or probability in this guide as hypothetical unless it comes directly from the stated position or calculation.
Define the problem precisely
Define variables, domains, and constraints from the puzzle before propagating. A domain reduction is sound only if every removed value violates a stated constraint given current assignments. Preserve the reason so an incorrect clue translation or assumption can be reversed.
Use a queue of variables or constraints changed by each deduction. For an all-different group, assigning one value removes it from peers. For an order relation X before Y, domain bounds can tighten. More advanced consistency levels remove values only under their defined support tests.
Use a repeatable process
Initialize domains, apply direct clues, enqueue affected constraints, and process them until the queue is empty. If a domain becomes empty, locate the assumption or earlier deduction causing contradiction. If several values remain, propagation has reached a fixed point rather than failed.
At a fixed point, search may be appropriate: choose a variable, assume one candidate, propagate, and backtrack on contradiction. Label the branch so hypothetical consequences are never mixed with unconditional deductions. A useful branch choice is a heuristic, not a puzzle rule.
Know what the result means
Basic propagation does not solve every valid puzzle, and a fixed point does not establish that every remaining value participates in a complete solution. Stronger consistency or search costs more work. No method here promises a puzzle success rate or completion time.
Constraints define validity. Propagation derives local consequences. Search explores alternatives. A transposition table in game programming caches previously examined states; it is a software technique and not required for a human pencil-and-paper solution.
Review and transfer the skill
Audit a solution by tracing each eliminated value to a constraint and current assignment. If a branch contradicts, restore the exact pre-branch domains before trying another value. Retaining branch marks prevents accidental conclusions from a discarded hypothesis.
The queue-and-domain approach supports Sudoku, matching, scheduling, and escape-room logic design. Each application must define its variables and constraints honestly; an algorithm cannot repair missing or ambiguous puzzle rules by itself.
Worked example: constraint propagation
In a hypothetical three-slot puzzle, variables A, B, and C each start with domain {1,2,3}, all values must differ, A is fixed at 2, and B must be less than C.
- Assign A=2 and propagate all-different, removing 2 from B and C so both domains become {1,3}.
- Apply B<C: B=3 has no supporting larger value for C, so remove 3 from B.
- B is now fixed at 1; propagate all-different again and remove 1 from C.
- C becomes 3, then verify A=2, B=1, C=3 against both original constraints.
constraint propagation worksheet
Use this reusable record to make the evidence and decisions behind constraint propagation visible for later review.
- Variables, initial domains, exact constraints, clue wording, and model assumptions.
- Direct assignments, removed values, supporting constraint, and affected-variable queue.
- Domain snapshots at each fixed point and any constraint lacking sufficient support.
- Branch label, assumed value, propagated effects, contradiction, and restoration snapshot.
- Final assignment, original-constraint verification, uniqueness status, and unresolved alternatives.
Common mistakes
- Removing a candidate because it feels unlikely without showing which stated constraint excludes it.
- Treating a propagation fixed point as proof that the puzzle has no solution or that one candidate is best.
- Backtracking from a contradiction without restoring every domain changed inside the discarded branch.
Try one
Propagation stops with two candidates in several cells and no empty domain. What has been established?
Only that the chosen propagation rules reached a fixed point with those candidates still locally supported. The puzzle may require a stronger deduction or labeled search. Do not choose a candidate randomly or claim the remaining values all extend to complete solutions.
Sources
- Chess Programming Wiki: SearchA technical index of game-tree search methods used in chess programming and related engines.
- Chess Programming Wiki: Transposition TableA technical reference on caching previously searched positions in game-tree programs.