Constraint Guided Backtracking¶

Solve a constrained, path-dependent problem by extending a partial solution, testing it early, and undoing the latest failed commitment while preserving still-valid prior work.

Constraint-guided backtracking is the solution pattern for problems that must be built step by step, where a later constraint may prove that the most recent step cannot work. The core move is not simply to “undo.” It is to preserve the still-valid prefix, abandon only the failed branch, and try the next alternative with the failure reason recorded.

Why this is not just rollback¶

Rollback by itself restores a previous state. Backtracking uses rollback as part of search. A partial solution is deliberately extended, tested, and reversed when a constraint proves that the branch cannot complete. This keeps valid prior work alive while avoiding both blind enumeration and irreversible lock-in.

Key components¶

Component	Description
Partial Solution State ↗	The partial solution state is the inspectable prefix: the variable assignments, planned steps, design decisions, diagnosis assumptions, or proof steps currently believed to be valid. It must expose enough structure for constraints to be tested before completion.
Decision Stack ↗	The decision stack records the ordered commitments that led to the current state. It allows the system to identify the newest reversible commitment and makes rollback disciplined rather than arbitrary.
Extension Operator ↗	The extension operator defines legal next moves. In a formal solver it may choose the next variable and value. In a human workflow it may propose the next design decision, diagnostic test, intake answer, or planning commitment.
Constraint Failure Test ↗	The constraint failure test decides when a branch can no longer lead to a valid completion. Good tests are explicit enough to distinguish a genuine failure from mere dislike, uncertainty, or inconvenience.
Rollback Rule ↗	The rollback rule says how far to step back. The ordinary case is chronological rollback to the latest choice. A stronger conflict explanation may justify deeper rollback when an earlier dependency, not the latest choice, caused the failure.
Visited Branch Record ↗	A visited branch record prevents cycling. It preserves which branches were tried, why they failed, and whether they should remain closed if constraints change later.

Common mechanisms¶

Recursive depth-first backtracking is the familiar computational mechanism: extend, recurse, fail, return, and try the next value. Constraint-satisfaction solver passes use the same logic with variables, domains, and constraints. Human-facing workflows often instantiate the archetype through undo-stack protocols, branch-history panels, decision-tree diagrams, contradiction logs, and structured step-back reviews.

Parameter dimensions¶

Important tuning dimensions include branch order, rollback depth, constraint-checking cost, completeness requirement, state preservation fidelity, audit depth, and escalation threshold. A domain can choose a fast heuristic branch order, a fairness-preserving order, an information-gain order, or a risk-first order, but the choice should be explicit.

Invariants to preserve¶

The archetype should preserve soundness, state consistency, valid-prefix retention, traceability, and completeness awareness. It should also preserve safety and rights constraints that are not merely search preferences.

Target outcomes¶

A good implementation reduces restart waste, detects infeasibility earlier, avoids greedy lock-in, and leaves a reviewable map of dead ends and open alternatives. It should make the search more learnable, not just more exhaustive.

Boundary notes¶

The closest accepted neighbor is bounded_search_pruning, because branch-and-bound is a child of backtracking in the prime ontology and is already directly covered there. The distinction is that bounded pruning excludes branches through bounds and objective dominance, while this archetype covers the more general reversible partial-solution search skeleton. checkpoint_and_rollback is also close, but its rollback is a recovery pattern rather than the normal rhythm of search.

Examples¶

In a scheduling problem, assignments are added one at a time until a rest-period or skill-coverage constraint fails; the latest incompatible assignment is removed and another candidate is tried. In debugging, a suspected cause path is explored until evidence contradicts it; the team records the contradiction and resumes from the last verified fork. In design, a team backs out a screen-flow decision after an accessibility constraint fails while preserving validated information architecture.

Non-examples¶

A production deployment rollback is usually checkpoint_and_rollback. A broad eligibility screen is usually search_space_pruning. A readiness review that sends a project back a phase is usually stage_gate_progression. Random trial-and-error without preserved state, failure records, and alternative branches is not this archetype.

Review posture¶

This is a merge-sensitive draft because several existing archetypes cover nearby search and rollback machinery. The draft is still warranted because the target prime has zero current coverage and because no existing archetype combines partial-state construction, constraint-triggered failure, minimal rollback, prefix preservation, and alternative-branch retry as the central intervention.

Common Mechanisms¶

chronological_backtracking_log
Constraint-Satisfaction Solver Pass — Encodes the commitments as a formal constraint model and runs a solver that propagates them to a reduced feasible region — or mechanically detects that no joint solution exists.
decision_tree_search_diagram
forward_checking_table
hypothesis_tree_review
recursive_depth_first_backtracking
undo_stack_protocol

Compression statement¶

When a solution must be built from interdependent choices and some constraints become visible only after partial construction, represent the current partial solution explicitly, extend it one reversible step at a time, test each extension against constraints or evidence, abandon a branch as soon as it cannot lead to success, roll back to the most recent useful decision point, record the failure reason, and try the next viable branch until completion, exhaustion, or method switch.

Canonical formula: State S_k = extend(S_{k-1}, choice c_k). If constraints(S_k) pass, continue; if fail, record cause, undo c_k or the implicated suffix, preserve valid prefix S_j, and try next c in alternatives(S_j). Stop when complete(S_n), alternatives exhausted, or escalation rule fires.

Abstractions this archetype builds on — directly (a source ingredient) or as a related pattern. Links follow the typed catalog namespace.

Built directly on (7)

Algorithm: Step-by-step problem-solving procedure.
Backtracking: Extend a partial solution one step at a time and reverse the most recent commitment as soon as a constraint proves it cannot succeed, preserving earlier work.
Constraint: Limits possibilities to guide outcomes.
Recursion: Breaks processes into self-similar steps.
Search and Retrieval: Locate and extract information.
Sequencing: Deliberately ordering steps under precedence constraints so that the arrangement itself, not just the set of tasks, determines the outcome.
State and State Transition: Captures system condition and evolution.

Also references 23 related abstractions

Approximation: Good-enough representation.
Boundedness: Values remain within limits.
Branch and Bound: Systematic search with pruning.
Closure: Ensures operations remain within a set.
Completeness: No gaps in structure.
Complexity: Measures system intricacy.
Decision: Committing to one alternative from a set under uncertainty and trade-off, collapsing open deliberation into a chosen path and foreclosing the others.
Dependency: Directed relation in which one element relies on another being present, prior, compatible, or supplied, with a specifiable failure mode if the condition is unmet.
Discreteness: Countable steps.
Eventual Consistency: Distributed copies of shared state are allowed to diverge under local updates, with a deterministic merge guaranteeing they reconverge once updates stop.

▸ Show 13 more

Variants¶

Narrower or domain-specific specializations that share this archetype's core structure. Recognized variants are established; candidate variants are provisional.

Recursive Constraint-Satisfaction Backtracking · domain variant · recognized

Applies recursive backtracking to assign values in a constraint-satisfaction problem while undoing infeasible assignments.

Distinct from parent: Narrower than the parent because it uses formal constraint-satisfaction machinery and often a recursive implementation.
Use when: A problem can be represented as variables, candidate values, and constraints; Constraint violations can be detected before a full solution is complete; A depth-first or recursive search structure is acceptable for the evaluation budget.
Typical domains: computer science, operations research, scheduling, logic puzzles
Common mechanisms: recursive depth first backtracking, constraint satisfaction solver pass, forward checking table

Diagnostic Hypothesis Backtracking · domain variant · candidate

Explores an explanatory path or hypothesis tree, then retracts the latest assumption when evidence contradicts it.

Distinct from parent: Narrower than the parent because its constraints are evidentiary and explanatory rather than purely formal.
Use when: A diagnosis depends on a sequence of assumptions, tests, or investigative moves; New evidence can falsify the most recent explanatory branch while preserving earlier observations; The team needs a trace of tried paths to avoid cycling or confirmation bias.
Typical domains: medicine, software debugging, incident response, legal investigation
Common mechanisms: hypothesis tree review, contradiction log, diagnostic branch map

Design Commitment Backtracking · implementation variant · candidate

Builds a design or plan through reversible commitments, undoing the latest incompatible choice while preserving earlier compatible structure.

Distinct from parent: Narrower than the parent because it emphasizes human and organizational commitment management.
Use when: A design, plan, or architecture accumulates interdependent commitments; Some commitments are reversible and can be undone before wider lock-in; Compatibility constraints are discovered during construction rather than known entirely in advance.
Typical domains: software architecture, product design, policy design, urban planning
Common mechanisms: undo stack protocol, design decision record with reversal, dependency compatibility check

Interactive Workflow Backtracking · implementation variant · candidate

Allows a person or team to step back through a structured workflow when a downstream constraint reveals an earlier local choice was invalid.

Distinct from parent: Narrower than the parent because human usability, state visibility, and undo semantics are central.
Use when: A workflow has ordered steps with dependencies among choices; Downstream evidence reveals that a recent step must be revised; Users need to preserve valid earlier context rather than restart the entire process.
Typical domains: human computer interaction, case management, education, workflow design
Common mechanisms: wizard back button with state preservation, undo stack protocol, branch history panel

Near names: Backtracking Search, Recursive Backtracking, Depth-First Backtracking, Trial-and-Error with Rollback, Constraint-Guided Rollback Search, Chronological Backtracking.