BacktrackingSolver<State, Choice> class

A reusable backtracking search over states of type State reached by applying choices of type Choice.

Example:

// Subset-sum: find a subset of [nums] summing to [target].
final BacktrackingSolver<(int index, List<int> picked, int sum), int>
    solver = BacktrackingSolver<(int, List<int>, int), int>(
  choices: ((int, List<int>, int) s) => s.$1 < nums.length
      ? <int>[0, 1] // skip or take the item at index s.$1
      : <int>[],
  apply: ((int, List<int>, int) s, int take) => take == 1
      ? (s.$1 + 1, <int>[...s.$2, nums[s.$1]], s.$3 + nums[s.$1])
      : (s.$1 + 1, s.$2, s.$3),
  isValid: ((int, List<int>, int) s) => s.$3 <= target,
  isComplete: ((int, List<int>, int) s) => s.$3 == target,
);
final (int, List<int>, int)? hit = solver.solveFirst((0, <int>[], 0));
Annotations

Constructors

BacktrackingSolver({required Iterable<Choice> choices(State), required State apply(State, Choice), required bool isComplete(State), required bool isValid(State)})
Creates a solver from the four pure callbacks that define the search:
const

Properties

apply → State Function(State, Choice)
The state reached by applying a choice to a state (no mutation). Audited: 2026-06-12 11:26 EDT
final
choices → Iterable<Choice> Function(State)
Candidate choices available from a given state. Audited: 2026-06-12 11:26 EDT
final
hashCode → int
The hash code for this object.
no setterinherited
isComplete → bool Function(State)
Whether a state is a complete, accepted solution. Audited: 2026-06-12 11:26 EDT
final
isValid → bool Function(State)
Whether a partial state is still valid (worth descending into). Audited: 2026-06-12 11:26 EDT
final
runtimeType → Type
A representation of the runtime type of the object.
no setterinherited

Methods

noSuchMethod(Invocation invocation) → dynamic
Invoked when a nonexistent method or property is accessed.
inherited
solveAll(State initial, {int? limit}) → List<State>
Returns up to limit complete solutions reachable from initial, in discovery (depth-first) order. A null limit collects every solution. Audited: 2026-06-12 11:26 EDT
solveFirst(State initial) → State?
Returns the first complete solution reachable from initial, or null if the search exhausts every valid branch without finding one. Audited: 2026-06-12 11:26 EDT
toString() → String
A string representation of this object.
inherited

Operators

operator ==(Object other) → bool
The equality operator.
inherited