Forward-Checking Table¶
Test or assessment — instantiates Constraint-Guided Backtracking
A table that, after each tentative commitment, recomputes the surviving legal options for every undecided part and flags a doomed branch the moment any part runs out.
A Forward-Checking Table is a look-ahead feasibility test: a grid that, the instant a tentative commitment is made, recomputes for every still-undecided part the set of options that remain legal, and raises the alarm the moment any part's option set drops to empty — signalling that this branch is already doomed, before the search wastes effort descending into it. Its distinguishing idea is that the test is prospective, not retrospective: it does not ask "is the current partial state consistent so far?" but "will each remaining slot still have at least one thing to fill it?" A branch can be perfectly consistent today and provably hopeless tomorrow, and the table is what sees the second condition early.
Example¶
A host is arranging a dinner for eight at a round table under a handful of constraints: two guests who feud must not sit adjacent, a toddler must sit beside a parent, and two guests insist on the window side. The host keeps a table with one row per unseated guest and columns for the seats still open; each cell marks whether that guest could still legally take that seat.
Tentatively seat guest A at seat 1. Forward checking runs immediately: for A's feuding partner B, seats 2 and 8 (the neighbors of seat 1) are struck out. Seat another guest and more cells vanish. Then, after seating guest C, the toddler's entire row goes blank — every remaining seat is now non-adjacent to a parent. That empty row is the verdict: this branch cannot complete no matter how the last five guests are placed. The host learns it now, backs C out, and tries a different seat for C — instead of laboriously placing all five and only then discovering the impossibility. The table proposes nothing and seats no one; it just tells the search, early, which branch is already dead.
How it works¶
- Maintain a live option set for each undecided part — the values still legal given every commitment so far.
- Probe after each extension. When a tentative commitment is made, propagate its consequences into the neighboring parts' option sets and delete any newly illegal values.
- Watch for a wipeout. If any part's option set empties, emit the failure signal: the current branch cannot be completed.
- Restore on retreat. When the search rolls the commitment back, the struck options are reinstated, since they were only illegal because of that commitment.
Tuning parameters¶
- Propagation strength — stop at directly affected neighbors, or cascade further toward full arc-consistency. Deeper propagation catches subtler dead ends at more cost per step.
- Which parts to track — every undecided part, or only the most-constrained handful. Tracking all is thorough; tracking few is cheap and often enough.
- Probe eagerness — run after every extension or only every few. Eager probing fails faster; lazy probing spends less on easy stretches.
- Cost budget — a cap on look-ahead effort per commitment, so the test never costs more than the descent it saves.
When it helps, and when it misleads¶
Its strength is early pruning: on tightly constrained problems it collapses huge doomed subtrees before the search ever enters them, turning many pointless descents into a single struck-out cell. The savings grow exactly where naive backtracking suffers most.
Its defining limitation is that forward checking is incomplete: a non-empty table is not a proof of solvability. It only looks one commitment deep into each neighbor, so a conflict that emerges two moves out slips past it — which is why maintaining full arc consistency prunes more, at more cost.[n1] The classic misuse is reading "no empty row yet" as "this branch is fine" and committing hard on that basis. The guarding discipline is to treat the table as a cheap early-warning filter that only ever reports doom, never safety, and to keep the actual search (and, at scale, a full Constraint-Satisfaction Solver Pass) responsible for proving a branch can complete.
How it implements the components¶
The Forward-Checking Table fills the look-ahead-and-fail slice of the archetype — detecting dead branches early, without steering the search itself:
forward_checking_probe— the per-commitment recomputation of every undecided part's surviving options is the probe: a bounded look-ahead into what the new commitment forecloses.constraint_failure_test— an emptied option set is the failure verdict; the table decides a branch is dead the instant any part has nothing legal left.
It does not extend the state or roll anything back — extension_operator and rollback_rule drive Recursive Depth-First Backtracking. And it does not escalate a hard call to a person: human_review_escape_hatch belongs to Hypothesis-Tree Review, its nearest twin among the archetype's tests — where this table is an automated, predictive wipeout check, that review is a human, retrospective judgment about genuine refutation.
Related¶
- Instantiates: Constraint-Guided Backtracking — the table is the archetype's optional look-ahead that turns constraint checking into early pruning.
- Sibling mechanisms: Recursive Depth-First Backtracking · Undo-Stack Protocol · Chronological Backtracking Log · Decision-Tree Search Diagram · Hypothesis-Tree Review · Constraint-Satisfaction Solver Pass — the full solver pass automates this same look-ahead across a whole formal model.
Editorial Notes¶
Form Classification¶
Form family: Control, Automation & Runtime
Rationale: Forward-Checking Table operates as a live operational control that automatically routes, enforces, adapts, or responds during execution because it a table that, after each tentative commitment, recomputes the surviving legal options for every undecided part and flags a doomed branch the moment any part runs out.
Independent corroboration: The frozen evidence defines Forward-Checking Table as 'A table that, after each tentative commitment, recomputes the surviving legal options for every undecided part and flags a doomed branch the moment any part runs out', so its operative form is Control, Automation & Runtime.
Nearest alternative: Analysis, Modeling & Optimization — Option propagation and branch wipeout detection execute live during search, while the table displays surviving domains.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Multi-domain
Rationale: Forward checking is a canonical constraint-satisfaction algorithm that prunes domains after each assignment.
Related originating lineages:
- Mathematics — Combinatorics and discrete constraint reasoning supply the underlying legal-option structure.
- Operations Research — Constraint programming and combinatorial optimization materially developed practical propagation tables.
Review resolution: Both reviewers agree that computer_science is primary. I retain operations_research, mathematics only as formative origin lineage(s), without treating every later application as an origin. single_lineage is appropriate because the evidence supports one principal professional lineage. Reach is multi_domain as a separate applicability judgment: it does not widen or narrow the recorded provenance. Encyclopedia synthesis is false because the artifact is already established enough that encyclopedia-specific synthesis is not required. The secondary differences are reconciled with no unresolved primary-provenance ambiguity.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] Arc consistency (as maintained by algorithms such as AC-3, and by "maintaining arc consistency" during search) enforces that every value of every variable has a consistent partner in each neighbor, pruning far more than one-step forward checking — at the price of more work per node. Forward checking is the cheaper, shallower cousin, and unlike full consistency it can leave conflicts undetected until a later commitment. ↩