backtrack
backtrack<
TState>(initialState,traits):BacktrackResult
Defined in: optimize/backtrack.ts:52
Depth-first search over a mutable state space, restoring the caller’s state on the way back out of every abandoned branch.
Unlike dfs, which only reads a structure, this owns an apply/undo
pair: the caller keeps one mutable world, apply advances it into a
candidate and undo rewinds it, so no state is ever copied. That is what
makes it the shape constraint problems (sudoku, N-queens, packing) need.
Time complexity: O(b^d) in the branching factor and depth — this is an
exhaustive search, bounded only by isGoal and isExhausted.
Type Parameters
Section titled “Type Parameters”TState
Section titled “TState”TState extends DefinedValue
Parameters
Section titled “Parameters”initialState
Section titled “initialState”TState | undefined
The state to search from, or undefined to start from
whatever candidatesOf(undefined) yields.
traits
Section titled “traits”BacktrackTraits<TState>
How to expand, mutate and test a state.
Returns
Section titled “Returns”true if a goal state was found, false if the space was exhausted
without one, or BacktrackExhausted if a branch reported itself
exhausted first.