Local Search with Backtracking¶
Search procedure — instantiates Oriented Goal Wayfinding
Explores one neighboring move at a time, marking dead ends and retracting a single step when blocked — depth-first search with undo.
Local Search with Backtracking finds a way through by committed trial with cheap undo. At the current position it generates the set of neighboring moves, picks one, and advances; if that branch dead-ends or violates a constraint, it marks the branch as exhausted and retracts a single step to the nearest point that still has an untried option. Its defining idea is that all the work happens at the step level: it never re-plans the whole route or reasons about the global map — it just decides the next neighbor and remembers how to take one step back. That locality is what makes it simple, complete in finite spaces, and immune to needing an overview — and also what makes it thrash when the space is large.
Example¶
A visitor enters a formal hedge maze with no plan and solves it the honest way. At each junction she surveys the immediate openings — the local candidate moves — and commits to one, say the leftmost she has not tried. She keeps going down that corridor. When it dead-ends at a wall, she does not despair or try to picture the whole maze; she chalks a small X on the dead branch so she will not re-enter it, then walks back to the last junction that still has an unexplored opening and takes the next one. Junction by junction, mark by mark, step back by single step, the marked dead ends fence off the exhausted parts of the maze until the only unmarked corridor left is the one that reaches the center. She never held a map; she only ever knew her neighbors and how to undo one move.
How it works¶
The procedure is a depth-first loop over a stack of decision points. At the current node it enumerates candidate neighbor moves and orders them by some cheap local heuristic (nearest to the goal, leftmost, least-recently-tried). It commits to the top choice and advances, pushing the decision onto the stack. Two things can end a branch: a dead end, or a constraint violation. Either way, the branch is marked exhausted and the procedure pops back exactly one decision point — the nearest ancestor with an untried option — and tries the next candidate there. The dead-end marks guarantee it never re-enters a branch it has already ruled out, which is what gives the search its completeness in a finite space: it will find a path if one exists, because it methodically exhausts alternatives without repeating them.
Tuning parameters¶
- Neighbor ordering — the heuristic that ranks candidate moves at each node. A good order reaches the goal fast; a bad one explores half the space first, though either eventually succeeds.
- Backtrack granularity — retract one step, or jump back several to a chosen decision point (backjumping). Deeper jumps escape traps faster but can skip untried options.
- Dead-end marking — how much of a failed branch to mark exhausted. Marking too coarsely can fence off ground that was actually passable by another approach.
- Commitment depth — how far to push down a promising branch before reconsidering. More commitment is efficient when the heuristic is trusted, wasteful when it is not.
- Cycle detection — how aggressively to spot and cut loops back to already-visited nodes.
When it helps, and when it misleads¶
Its strength is that it needs no overview and no map — only a notion of the local neighbors, a test for dead ends, and cheap reversibility. In discrete, well-bounded spaces it is complete: it will find a path if one exists, exactly because dead-end marks stop it re-treading ruled-out ground. It is the workhorse of constraint solving and maze-running, formalized as depth-first search with backtracking.[n1]
Its failure mode is combinatorial explosion: in a large branching space the number of paths to try grows brutally, and a search that is complete in principle can be hopeless in practice, thrashing near local traps and revisiting near-identical states. It also assumes moves are reversible — that stepping back costs little — which is false when a wrong move is irreversible or expensive. The classic misuse is turning local search loose on a space too big for it and waiting for a solution that will not arrive in time. The guarding discipline is to bound the depth, add a global heuristic to guide the ordering, and escalate to whole-route re-planning when local search stalls rather than letting it grind.
How it implements the components¶
candidate_move_set— its engine: at each node it generates and orders the set of neighboring moves to try.backtracking_and_reroute_rule— the backtrack half of that rule: pop the last committed step and try an untried neighbor at the nearest live decision point.hazard_and_dead_end_marker— exhausted branches are marked so the search never re-enters them, which underwrites its completeness.
It does not implement incomplete_map_boundary-driven whole-route re-synthesis — abandoning the entire path and computing a fresh route from the global map is route_replanning; local search only retracts one step and tries the next neighbor. Nor does it own recalibration_checkpoint — snapping a position estimate to a reference map is map_matching_and_recalibration.
Related¶
- Instantiates: Oriented Goal Wayfinding — it fills the loop's move-generation and step-level recovery roles.
- Consumes: breadcrumb_trail — it reads the trail's record and dead-end tags to know which ground is already exhausted.
- Sibling mechanisms: dead_reckoning_loop · guided_traversal_protocol · landmark_based_wayfinding · map_matching_and_recalibration · orientation_overlay · route_replanning · turn_by_turn_route_guidance · waypoint_decomposition
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: The algorithm explores neighboring moves, marks dead ends, and backtracks to compute a feasible search path.
Nearest alternative: Protocol, Workflow & Routine — Moves occur in sequence, but the operative mechanism is algorithmic search rather than actor workflow.
Review outcome: Adjudicated after independent review; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Universal
Rationale: Depth-first local search with explicit undo at dead ends is a canonical computer-science search procedure.
Related originating lineages:
- Mathematics — Combinatorial search and proof trees materially supply the formal finite-space structure.
Review resolution: Both independent reviews assign primary provenance to computer_science. The queued secondary differences (alternate_origin_disagreement, origin_mode_disagreement, domain_reach_disagreement) are reconciled by retaining mathematics only as formative or independently established lineage(s), not merely as application domains. origin_mode=cross_disciplinary_synthesis records the provenance relationship, while domain_reach=universal separately records applicability breadth. confidence=high preserves the more cautious assessment, and encyclopedia_synthesis=false records whether either reviewer identified a corpus-specific synthesis.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] Depth-first search with backtracking explores a branch fully before retreating: it commits to one option, recurses, and on failure "backtracks" to the most recent decision point with an untried alternative. Marking exhausted branches prevents repetition and makes the search complete in finite spaces — the same skeleton underlies constraint solvers and maze-solving algorithms. ↩