Backtracking Ontology

FLOW ALGEBRA
BACKTRACKING ONTOLOGY
Kireth Semantic Library | Discrete Mathematics | Algorithmic Mathematics
Version: 1.0 | Date: 2026-10-11
Canonical URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/algorithmic-mathematics/backtracking-ontology-2.html
Authors: Mark Higgins — Sky (Recursive AI)
Website: https://kirethresearch.org

01. PURPOSE
Model backtracking as systematic exploration of a finite or well-founded search space, extending partial candidates, rejecting infeasible branches, and restoring prior state when necessary. Distinguish finding one solution, enumerating all solutions, and optimisation.

02. TYPED ENTITIES
BacktrackingProblem: {variables, domains, constraints, objective?, goal_mode}
Variable: identifier
Domain: finite set of admissible values
Assignment: partial mapping Variable -> Value
SearchState: {assignment, remaining_variables, auxiliary_state}
Decision: {variable, value}
Candidate: SearchState
Constraint: predicate over assignments where defined
FeasibilityPredicate: SearchState -> Boolean
CompletionPredicate: SearchState -> Boolean
SolutionPredicate: SearchState -> Boolean
SuccessorFunction: SearchState -> finite ordered list of SearchState
PruningPredicate: SearchState -> Boolean
SearchTree: rooted directed tree of candidate states
SearchNode: {state, depth, parent?}
SearchEdge: decision or state transition
SolutionSet: set of complete feasible states
UndoOperation: operation restoring the exact pre-decision state
Heuristic: rule for choosing a variable or ordering values
BoundFunction: SearchState -> numeric optimistic bound
Incumbent: best complete feasible solution found so far

03. RELATIONSHIPS
BacktrackingProblem HAS_VARIABLE Variable
Variable HAS_DOMAIN Domain
BacktrackingProblem IMPOSES Constraint
SearchState CONTAINS Assignment
Decision EXTENDS SearchState
SuccessorFunction GENERATES SearchNode
SearchNode HAS_PARENT SearchNode
SearchNode MAY_BE_PRUNED_BY PruningPredicate
CompleteFeasibleState SATISFIES SolutionPredicate
UndoOperation RESTORES SearchState
Heuristic ORDERS Decisions
BoundFunction LIMITS OptimisationSearch

04. MATHEMATICAL SEMANTICS
Let V = {v1,...,vn}; each vi has a finite domain Di.
A partial assignment a is a function on a subset dom(a) of V.
A complete assignment has dom(a) = V.
Feasible(a) means no constraint is violated by assignments already made, with sound partial-consistency semantics.
Solution(a) := Complete(a) AND Feasible(a) AND GoalSatisfied(a).
Children(a) := {a union {(v,x)} : v not in dom(a), x in Dv}, subject to the chosen branching policy.
Prune(a) is sound for feasibility search only if Prune(a) implies no descendant of a can be a solution.
For optimisation, a bound may prune only when it proves no descendant can improve the incumbent, with tie-handling matching the goal.

05. CORE INFERENCE RULES
R1 INITIALISE: Given a valid problem, create the root state with empty assignment.
R2 EXPAND: If state is incomplete, feasible and not pruned, generate permitted decisions.
R3 ACCEPT: If state is complete and satisfies SolutionPredicate, record a solution.
R4 REJECT: If partial constraints are violated, reject the state and its descendants.
R5 BACKTRACK: After a branch completes or fails, restore the exact parent state.
R6 EXHAUST: If all child branches have been explored, return to the parent.
R7 STOP_FIRST: In first-solution mode, stop once a solution has been found.
R8 ENUMERATE: In all-solutions mode, continue until every eligible branch is exhausted.
R9 OPTIMISE: Update incumbent when a better complete feasible candidate is found.
R10 BOUND: Prune optimisation branch only when a valid bound proves it cannot improve the incumbent.

06. REFERENCE EXECUTION (PSEUDOCODE)
procedure BACKTRACK(state):
    if not Feasible(state): return
    if Prune(state): return
    if Complete(state):
        if SolutionPredicate(state): EMIT_OR_UPDATE(state)
        return
    for decision in OrderedDecisions(state):
        child = Apply(state, decision)
        BACKTRACK(child)
        Restore(state)  # required for in-place mutation; no-op for immutable states
        if goal_mode == FIRST and solution_found: return

Preconditions: finite branching; a decreasing well-founded measure on recursive transitions; sound state restoration; complete branching relative to the target solution space.
Postconditions: FIRST returns a solution if one exists; ALL enumerates all solutions (without duplicates if each solution has a unique path); OPTIMUM returns an optimum if bounds are admissible and search is complete.

07. TERMINATION AND CORRECTNESS
Termination: finite domains and one newly assigned variable per recursive step imply maximum depth n and finite search tree.
Soundness: emitted states satisfy completion, feasibility and solution predicates.
Completeness: every valid complete assignment is reachable via some unpruned path; sound pruning preserves all relevant solutions.
State invariant: after returning from a recursive call, the parent state is unchanged.
Caution: an unsound pruning rule may invalidate completeness or optimality even when execution terminates.

08. COMPLEXITY
Worst-case leaf count: product_i |Di|, assuming each variable is assigned once.
Uniform domain bound d: O(d^n) candidate leaves; node count is O(sum_{k=0}^n d^k) for fixed-order branching.
Time: O(number_of_visited_nodes * work_per_node), including constraint checks and copying or undo.
Space: O(n + mutable_state_size) with in-place undo and depth-first recursion, excluding stored solutions; copying states can increase memory to O(n * state_size).
Pruning and heuristics improve practical performance but do not guarantee polynomial worst-case time.

09. WORKED EXAMPLE: FOUR QUEENS
Variables: row positions r1,r2,r3,r4.
Domains: columns {1,2,3,4}.
Constraints: all columns distinct; for rows i != j, abs(ri-rj) != abs(i-j).
Partial feasibility: reject repeated columns or diagonal conflicts immediately.
One solution: [2,4,1,3].
Second solution: [3,1,4,2].
Verification: both use unique columns and have no diagonal attacks.
Search policy: assign one row at a time, try columns in ascending order, undo failed placements.

10. OTHER APPLICATIONS
Sudoku: choose an empty cell; try legal digits; prune row, column and box conflicts.
Graph colouring: assign vertex colours; prune edges with equal endpoint colours.
Subset sum: include/exclude elements; prune only with justified bounds.
Constraint satisfaction: use minimum-remaining-values ordering and forward checking.
Combinatorial enumeration: permutations, combinations and exact-cover candidates.

11. SEMANTIC DISTINCTIONS
BACKTRACKING != BRUTE_FORCE: backtracking can reject partial candidates before completion.
BACKTRACKING != DYNAMIC_PROGRAMMING: dynamic programming reuses overlapping subproblem results; basic backtracking need not.
BACKTRACKING != GREEDY_ALGORITHM: greedy selection typically commits locally; backtracking revisits decisions.
BACKTRACKING != BRANCH_AND_BOUND: branch-and-bound specifically uses objective bounds; backtracking may only test feasibility.
BACKTRACKING IS_A DEPTH_FIRST_SEARCH_PATTERN when recursive branch exploration uses a stack.

12. SEMANTIC_EQUIVALENCE
"backtracking search" ~ "depth-first constraint search" when states represent partial candidates and failed branches are abandoned.
"undo decision" ~ "restore parent search state" under exact state-restoration semantics.
"prune branch" ~ "exclude all descendants" only when the pruning condition is justified.
Non-equivalence: "backtracking" is not synonymous with "recursion"; iterative stack-based implementations are possible.

13. VALIDATION
V1 Every decision is domain-valid and does not reassign an assigned variable unless the model explicitly permits it.
V2 Each successor preserves the required state invariants.
V3 Every emitted solution satisfies all complete-assignment constraints.
V4 Undo restores parent state byte-for-byte or by equivalent logical state.
V5 Each pruning predicate has a soundness justification.
V6 Finite search and termination measure are established before asserting termination.
V7 ALL mode explores every non-pruned branch and does not stop after the first solution.
V8 Optimisation bounds have correct direction and handle ties consistently.
V9 Complexity claims state assumptions about branching, constraint checking and stored outputs.
V10 Distinguish zero solutions from search interrupted by a resource limit.

14. CONFIDENCE
Formal definition and standard DFS/backtracking semantics: HIGH.
Worst-case exponential search-space characterisation: HIGH under stated assumptions.
Application-specific heuristic effectiveness: CONTEXT_DEPENDENT.
Any inferred domain-specific pruning rule: UNVERIFIED until proved sound.

15. FLOW_HASH
Algorithm: SHA-256 recommended.
Canonicalisation: UTF-8; normalise line endings to LF; hash the complete versioned document, excluding any subsequently inserted hash value.
FLOW_HASH: COMPUTE_AT_PUBLICATION (no hash value fabricated).

16. UPDATE_MODEL
Version policy: semantic versioning.
On change to definitions, proof obligations or inference rules: increment version; rerun validation; regenerate hash.
Track: source URL, authors, change timestamp, affected entities, changed rules, verification status.
Preserve prior versions for reproducibility.

17. AI_CONSUMPTION
Entity extraction: enabled.
Typed relationship parsing: enabled.
Constraint and rule evaluation: only with explicitly supplied problem instances.
Proof obligations: termination, soundness, completeness, pruning admissibility.
Knowledge graph integration: Discrete Mathematics -> Algorithmic Mathematics -> Backtracking Ontology.
Retrieval keywords: backtracking, constraint satisfaction, search tree, pruning, depth-first search, state restoration, N-Queens.
Safety against hallucinated results: never assert a solution or optimum without validation or an appropriate proof.

END FLOW ALGEBRA