Recursive depth-first backtracking over an implicit state space. More...

#include <Backtracking.H>

Collaboration diagram for Aleph::Depth_First_Backtracking< Domain >:

Public Types
using	Domain_Type = Domain
	Type of the problem domain.

using	State = typename Domain::State
	Concrete search state type.

using	Move = typename Domain::Move
	Move type.

using	Solution = SearchSolution< State, Move >
	Concrete solution type.

using	Solution_Compare = state_search_detail::PreferShallowerSolution< State, Move >
	Internal solution comparator.

using	Result = SearchResult< Solution, Solution_Compare >
	Aggregated result type.

Public Member Functions
	Depth_First_Backtracking (Domain domain, ExplorationPolicy policy={}, const SearchLimits &limits={}, Solution_Compare compare={})
	Build an engine bound to one domain adapter.

const Domain &	domain () const noexcept
	Read-only access to the bound domain adapter.

Domain &	domain () noexcept
	Mutable access to the bound domain adapter.

const ExplorationPolicy &	policy () const noexcept
	Current exploration policy.

const SearchLimits &	limits () const noexcept
	Current hard limits.

void	set_policy (const ExplorationPolicy &policy) noexcept
	Replace the exploration policy for future runs.

void	set_limits (const SearchLimits &limits) noexcept
	Replace the hard limits for future runs.

Result	search (State initial_state)
	Execute a depth-first backtracking search from `initial_state`.

template<typename OnSolution > requires SearchSolutionVisitor<OnSolution, Solution>
Result	search (State initial_state, OnSolution &on_solution)
	Execute DFS/backtracking and invoke `on_solution` on each solution.

template<typename OnSolution > requires SearchSolutionVisitor<OnSolution, Solution>
Result	search (State initial_state, OnSolution &&on_solution)
	Rvalue-friendly overload for temporary solution visitors.

template<typename VisitedSet > requires SearchStateKeyProvider<Domain>
and VisitedBoundMap< VisitedSet, typename Domain::State_Key, size_t > Result	search (State initial_state, VisitedSet &visited)
	DFS/backtracking with a depth-aware visited-state map.

template<typename VisitedSet , typename OnSolution > requires SearchStateKeyProvider<Domain>
and VisitedBoundMap< VisitedSet, typename Domain::State_Key, size_t > and SearchSolutionVisitor< OnSolution, Solution > Result	search (State initial_state, VisitedSet &visited, OnSolution &on_solution)
	DFS/backtracking with depth-aware visited-state tracking and a solution callback.

Static Public Attributes
static constexpr bool	supports_best_first = false
	Compile-time marker: Depth_First_Backtracking only supports Depth_First strategy.

Private Member Functions
bool	stop_after_solution (Result &result) const

bool	expansion_limit_reached (Result &result) const

template<typename OnSolution > requires SearchSolutionVisitor<OnSolution, Solution>
bool	dfs (State &state, SearchPath< Move > &path, const size_t depth, Result &result, OnSolution &on_solution)

template<typename OnSolution , typename VisitedSet > requires SearchSolutionVisitor<OnSolution, Solution>
and VisitedBoundMap< VisitedSet, typename Domain::State_Key, size_t > bool	dfs_visited (State &state, SearchPath< Move > &path, const size_t depth, Result &result, OnSolution &on_solution, VisitedSet &visited)

Private Attributes
Domain	domain_

ExplorationPolicy	policy_

SearchLimits	limits_

Solution_Compare	compare_

Detailed Description

template<BacktrackingDomain Domain>
class Aleph::Depth_First_Backtracking< Domain >

Recursive depth-first backtracking over an implicit state space.

The domain contract is given by Aleph::BacktrackingDomain. Goal states are treated as accepted solutions and are not expanded further. Domains may also expose optional is_terminal() and should_prune() hooks.

Template Parameters

Domain problem adapter exposing State, Move, successor generation and apply() / undo().

Definition at line 85 of file Backtracking.H.

Member Typedef Documentation

◆ Domain_Type

template<BacktrackingDomain Domain>

using Aleph::Depth_First_Backtracking< Domain >::Domain_Type = Domain

Type of the problem domain.

Definition at line 89 of file Backtracking.H.

◆ Move

template<BacktrackingDomain Domain>

using Aleph::Depth_First_Backtracking< Domain >::Move = typename Domain::Move

Move type.

Definition at line 93 of file Backtracking.H.

◆ Result

template<BacktrackingDomain Domain>

using Aleph::Depth_First_Backtracking< Domain >::Result = SearchResult<Solution, Solution_Compare>

Aggregated result type.

Definition at line 99 of file Backtracking.H.

◆ Solution

template<BacktrackingDomain Domain>

using Aleph::Depth_First_Backtracking< Domain >::Solution = SearchSolution<State, Move>

Concrete solution type.

Definition at line 95 of file Backtracking.H.

◆ Solution_Compare

template<BacktrackingDomain Domain>

using Aleph::Depth_First_Backtracking< Domain >::Solution_Compare = state_search_detail::PreferShallowerSolution<State, Move>

Internal solution comparator.

Definition at line 97 of file Backtracking.H.

◆ State

template<BacktrackingDomain Domain>

using Aleph::Depth_First_Backtracking< Domain >::State = typename Domain::State

Concrete search state type.

Definition at line 91 of file Backtracking.H.

Constructor & Destructor Documentation

◆ Depth_First_Backtracking()

template<BacktrackingDomain Domain>

Aleph::Depth_First_Backtracking< Domain >::Depth_First_Backtracking	(	Domain	domain,
		ExplorationPolicy	policy = `{}`,
		const SearchLimits &	limits = `{}`,
		Solution_Compare	compare = `{}`
	)

inlineexplicit

Build an engine bound to one domain adapter.

Parameters

domain	Problem adapter captured by value. Ownership is transferred into the engine; move-only domains are accepted and remain owned for the lifetime of the `Depth_First_Backtracking`.
policy	Exploration policy copied into the engine. Only `Depth_First` traversal is honored during search.
limits	Search constraints copied and enforced on every run (such as depth, expansions and solutions).
compare	Functor used to rank solutions kept by Result; moved into the result objects returned by search.

Exceptions

None.

Complexity: Time O(1); space O(1).

Thread Safety: Not thread-safe. Guard the engine externally when sharing across threads.

Definition at line 127 of file Backtracking.H.

Member Function Documentation

◆ dfs()

template<BacktrackingDomain Domain>

template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>

bool Aleph::Depth_First_Backtracking< Domain >::dfs	(	State &	state,
		SearchPath< Move > &	path,
		const size_t	depth,
		Result &	result,
		OnSolution &	on_solution
	)

inlineprivate

Definition at line 394 of file Backtracking.H.

References Aleph::Array< T >::append(), Aleph::SearchResult< Solution, Compare >::best_solution, Aleph::BestSolution< Solution, Compare >::consider(), Aleph::Depth_First_Backtracking< Domain >::dfs(), Aleph::divide_and_conquer_partition_dp(), Aleph::Depth_First_Backtracking< Domain >::domain_, Aleph::SearchStats::expanded_states, Aleph::Depth_First_Backtracking< Domain >::expansion_limit_reached(), Aleph::SearchStats::generated_successors, Aleph::search_engine_detail::is_terminal_state(), Aleph::Depth_First_Backtracking< Domain >::limits_, Aleph::SearchLimits::max_depth, Aleph::SearchStats::max_depth_reached, Aleph::SearchStats::pruned_by_depth, Aleph::SearchStats::pruned_by_domain, Aleph::Array< T >::remove_last(), Aleph::search_engine_detail::should_prune_state(), Aleph::SearchStats::solutions_found, Aleph::SearchResult< Solution, Compare >::stats, Aleph::SearchResult< Solution, Compare >::status, Aleph::Depth_First_Backtracking< Domain >::stop_after_solution(), Aleph::StoppedOnSolution, Aleph::SearchStats::terminal_states, and Aleph::SearchStats::visited_states.

Referenced by Aleph::Depth_First_Backtracking< Domain >::dfs(), and Aleph::Depth_First_Backtracking< Domain >::search().

◆ dfs_visited()

template<BacktrackingDomain Domain>

template<typename OnSolution , typename VisitedSet >
requires SearchSolutionVisitor<OnSolution, Solution>

and VisitedBoundMap< VisitedSet, typename Domain::State_Key, size_t > bool Aleph::Depth_First_Backtracking< Domain >::dfs_visited	(	State &	state,
		SearchPath< Move > &	path,
		const size_t	depth,
		Result &	result,
		OnSolution &	on_solution,
		VisitedSet &	visited
	)

inlineprivate

Definition at line 470 of file Backtracking.H.

Referenced by Aleph::Depth_First_Backtracking< Domain >::dfs_visited(), and Aleph::Depth_First_Backtracking< Domain >::search().

◆ domain() [1/2]

template<BacktrackingDomain Domain>

const Domain & Aleph::Depth_First_Backtracking< Domain >::domain ( ) const

inlinenoexcept

Read-only access to the bound domain adapter.

Returns: const Domain& view of the currently configured domain adapter.

Exceptions

None.

Complexity: Time O(1); space O(1).

Thread Safety: Caller must synchronize concurrent accesses to the engine.

Definition at line 144 of file Backtracking.H.

References Aleph::Depth_First_Backtracking< Domain >::domain_.

◆ domain() [2/2]

template<BacktrackingDomain Domain>

Domain & Aleph::Depth_First_Backtracking< Domain >::domain ( )

inlinenoexcept

Mutable access to the bound domain adapter.

Returns: Domain& reference that permits in-place configuration changes.

Exceptions

None.

Complexity: Time O(1); space O(1).

Thread Safety: Not thread-safe. Synchronize externally before mutating the domain.

Definition at line 157 of file Backtracking.H.

References Aleph::Depth_First_Backtracking< Domain >::domain_.

◆ expansion_limit_reached()

template<BacktrackingDomain Domain>

bool Aleph::Depth_First_Backtracking< Domain >::expansion_limit_reached ( Result & result ) const

inlineprivate

Definition at line 387 of file Backtracking.H.

References Aleph::search_engine_detail::expansion_limit_reached(), and Aleph::Depth_First_Backtracking< Domain >::limits_.

Referenced by Aleph::Depth_First_Backtracking< Domain >::dfs(), and Aleph::Depth_First_Backtracking< Domain >::dfs_visited().

◆ limits()

template<BacktrackingDomain Domain>

const SearchLimits & Aleph::Depth_First_Backtracking< Domain >::limits ( ) const

inlinenoexcept

Current hard limits.

Returns: const SearchLimits& currently enforced during search.

Exceptions

None.

Complexity: Time O(1); space O(1).

Thread Safety: Caller must synchronize concurrent observations.

Definition at line 183 of file Backtracking.H.

References Aleph::Depth_First_Backtracking< Domain >::limits_.

Referenced by Aleph::Depth_First_Backtracking< Domain >::set_limits().

◆ policy()

template<BacktrackingDomain Domain>

const ExplorationPolicy & Aleph::Depth_First_Backtracking< Domain >::policy ( ) const

inlinenoexcept

Current exploration policy.

Returns: const ExplorationPolicy& describing how successors are explored.

Exceptions

None.

Complexity: Time O(1); space O(1).

Thread Safety: Caller must synchronize concurrent observations.

Definition at line 170 of file Backtracking.H.

References Aleph::Depth_First_Backtracking< Domain >::policy_.

Referenced by Aleph::Depth_First_Backtracking< Domain >::set_policy().

◆ search() [1/5]

template<BacktrackingDomain Domain>

Result Aleph::Depth_First_Backtracking< Domain >::search ( State initial_state )

inline

Execute a depth-first backtracking search from initial_state.

Parameters

initial_state Mutable root state provided by value; the engine restores it before returning so callers retain ownership.

Returns: Result containing the final search status, aggregated statistics, effective limits/policy, and the best solution kept according to Solution_Compare.

Exceptions

std::invalid_argument if policy().strategy is not ExplorationPolicy::Strategy::Depth_First or if limits().max_solutions == 0.

Complexity: Time proportional to the number of visited states until termination; auxiliary space proportional to the maximum path depth (one stack of states plus bookkeeping in SearchPath).

Thread Safety: Not thread-safe. Serialize concurrent invocations on the same engine.

Definition at line 231 of file Backtracking.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Depth_First_Backtracking< Domain >::search().

Referenced by Aleph::Depth_First_Backtracking< Domain >::search(), Aleph::Depth_First_Backtracking< Domain >::search(), Aleph::Depth_First_Backtracking< Domain >::search(), and TEST().

◆ search() [2/5]

template<BacktrackingDomain Domain>

template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>

Result Aleph::Depth_First_Backtracking< Domain >::search	(	State	initial_state,
		OnSolution &&	on_solution
	)

inline

Rvalue-friendly overload for temporary solution visitors.

Parameters

initial_state	Mutable root state explored by value.
on_solution	Temporary visitor consumed (moved) by the call.

Returns: Result identical to the lvalue overload.

Exceptions

std::invalid_argument under the same conditions as the lvalue overload.

Complexity: Same as other search overloads.

Thread Safety: External synchronization required.

Definition at line 291 of file Backtracking.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Depth_First_Backtracking< Domain >::search().

◆ search() [3/5]

template<BacktrackingDomain Domain>

template<typename OnSolution >
requires SearchSolutionVisitor<OnSolution, Solution>

Result Aleph::Depth_First_Backtracking< Domain >::search	(	State	initial_state,
		OnSolution &	on_solution
	)

inline

Execute DFS/backtracking and invoke on_solution on each solution.

Parameters

initial_state	Mutable root state explored by value.
on_solution	Functor satisfying Aleph::SearchSolutionVisitor that receives immutable Solution snapshots and returns `true` to continue or `false` to stop immediately.

Returns: Result populated with policy, limits, statistics and the best solution according to Solution_Compare.

Exceptions

std::invalid_argument if the exploration policy is not depth-first or if limits().max_solutions == 0.

Complexity: Same as the overload without a callback: time proportional to explored states, auxiliary space proportional to max depth.

Thread Safety: External synchronization required.

Definition at line 255 of file Backtracking.H.

References ah_invalid_argument_if, Aleph::Depth_First_Backtracking< Domain >::compare_, Aleph::ExplorationPolicy::Depth_First, Aleph::Depth_First_Backtracking< Domain >::dfs(), Aleph::divide_and_conquer_partition_dp(), Aleph::SearchStats::elapsed_ms, Aleph::Exhausted, Aleph::SearchResult< Solution, Compare >::limits, Aleph::Depth_First_Backtracking< Domain >::limits_, Aleph::SearchLimits::max_solutions, Aleph::NotStarted, Aleph::SearchResult< Solution, Compare >::policy, Aleph::Depth_First_Backtracking< Domain >::policy_, Aleph::reserve_search_path(), Aleph::search_elapsed_ms(), Aleph::SearchResult< Solution, Compare >::stats, Aleph::SearchResult< Solution, Compare >::status, and Aleph::ExplorationPolicy::strategy.

◆ search() [4/5]

template<BacktrackingDomain Domain>

template<typename VisitedSet >
requires SearchStateKeyProvider<Domain>

and VisitedBoundMap< VisitedSet, typename Domain::State_Key, size_t > Result Aleph::Depth_First_Backtracking< Domain >::search	(	State	initial_state,
		VisitedSet &	visited
	)

inline

DFS/backtracking with a depth-aware visited-state map.

Converts tree-search to graph-search: states are marked globally after passing limit/pruning checks. A state is pruned only when a previous expansion reached it at an equal or shallower depth (i.e., with at least as much remaining budget); if the current path is shallower the stored depth is updated and exploration continues. Requires domains exposing state_key(state).

Parameters

initial_state	Mutable root state explored by value.
visited	Caller-managed depth map that accumulates visited keys across calls; must satisfy Aleph::VisitedBoundMap with `size_t` as the bound type (e.g. `SearchStorageMap<Key, size_t>`).

Returns: Result with final status, statistics, limits/policy snapshots and best solution backed by Solution_Compare.

Exceptions

std::invalid_argument if the exploration policy is not depth-first or if limits().max_solutions == 0.

Complexity: Time proportional to explored states; auxiliary space proportional to the maximum search depth and the size of visited.

Thread Safety: Caller must synchronize both the engine and the provided visited map.

Definition at line 323 of file Backtracking.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Depth_First_Backtracking< Domain >::search().

◆ search() [5/5]

template<BacktrackingDomain Domain>

template<typename VisitedSet , typename OnSolution >
requires SearchStateKeyProvider<Domain>

and VisitedBoundMap< VisitedSet, typename Domain::State_Key, size_t > and SearchSolutionVisitor< OnSolution, Solution > Result Aleph::Depth_First_Backtracking< Domain >::search	(	State	initial_state,
		VisitedSet &	visited,
		OnSolution &	on_solution
	)

inline

DFS/backtracking with depth-aware visited-state tracking and a solution callback.

Parameters

initial_state	Mutable root state explored by value.
visited	Caller-managed depth map updated at every state expansion; must satisfy Aleph::VisitedBoundMap with `size_t` as bound type (e.g. `SearchStorageMap<Key, size_t>`).
on_solution	Solution visitor invoked for each solution; returning `false` stops the search immediately.

Returns: Result capturing the final status, stats, limits, policy and best solution selected by Solution_Compare.

Exceptions

std::invalid_argument if the policy is not depth-first or if the configured maximum number of solutions is zero.

Complexity: Time proportional to explored states, auxiliary space proportional to the maximum depth plus storage required by visited.

Thread Safety: Not thread-safe. Synchronize external access to both the engine and the provided depth map.

Definition at line 352 of file Backtracking.H.

References ah_invalid_argument_if, Aleph::Depth_First_Backtracking< Domain >::compare_, Aleph::ExplorationPolicy::Depth_First, Aleph::Depth_First_Backtracking< Domain >::dfs_visited(), Aleph::divide_and_conquer_partition_dp(), Aleph::SearchStats::elapsed_ms, Aleph::Exhausted, Aleph::SearchResult< Solution, Compare >::limits, Aleph::Depth_First_Backtracking< Domain >::limits_, Aleph::SearchLimits::max_solutions, Aleph::NotStarted, Aleph::SearchResult< Solution, Compare >::policy, Aleph::Depth_First_Backtracking< Domain >::policy_, Aleph::reserve_search_path(), Aleph::search_elapsed_ms(), Aleph::SearchResult< Solution, Compare >::stats, Aleph::SearchResult< Solution, Compare >::status, and Aleph::ExplorationPolicy::strategy.

◆ set_limits()

template<BacktrackingDomain Domain>

void Aleph::Depth_First_Backtracking< Domain >::set_limits ( const SearchLimits & limits )

inlinenoexcept

Replace the hard limits for future runs.

Parameters

limits New SearchLimits copied verbatim into the engine.

Exceptions

None.

Complexity: Time O(1); space O(1).

Thread Safety: Synchronize externally when mutating shared engines.

Definition at line 209 of file Backtracking.H.

References Aleph::Depth_First_Backtracking< Domain >::limits(), and Aleph::Depth_First_Backtracking< Domain >::limits_.

◆ set_policy()

template<BacktrackingDomain Domain>

void Aleph::Depth_First_Backtracking< Domain >::set_policy ( const ExplorationPolicy & policy )

inlinenoexcept

Replace the exploration policy for future runs.

Parameters

policy Exploration policy copied and used by subsequent search calls.

Exceptions

None.

Complexity: Time O(1); space O(1).

Thread Safety: Synchronize externally when mutating shared engines.

Definition at line 196 of file Backtracking.H.

References Aleph::Depth_First_Backtracking< Domain >::policy(), and Aleph::Depth_First_Backtracking< Domain >::policy_.

◆ stop_after_solution()

template<BacktrackingDomain Domain>

bool Aleph::Depth_First_Backtracking< Domain >::stop_after_solution ( Result & result ) const

inlineprivate

Definition at line 382 of file Backtracking.H.

References Aleph::Depth_First_Backtracking< Domain >::limits_, Aleph::Depth_First_Backtracking< Domain >::policy_, and Aleph::search_engine_detail::stop_after_solution().

Referenced by Aleph::Depth_First_Backtracking< Domain >::dfs(), and Aleph::Depth_First_Backtracking< Domain >::dfs_visited().

Member Data Documentation

◆ compare_

template<BacktrackingDomain Domain>

Solution_Compare Aleph::Depth_First_Backtracking< Domain >::compare_

private

Definition at line 380 of file Backtracking.H.

Referenced by Aleph::Depth_First_Backtracking< Domain >::search(), and Aleph::Depth_First_Backtracking< Domain >::search().

◆ domain_

template<BacktrackingDomain Domain>

Domain Aleph::Depth_First_Backtracking< Domain >::domain_

private

Definition at line 377 of file Backtracking.H.

Referenced by Aleph::Depth_First_Backtracking< Domain >::dfs(), Aleph::Depth_First_Backtracking< Domain >::dfs_visited(), Aleph::Depth_First_Backtracking< Domain >::domain(), and Aleph::Depth_First_Backtracking< Domain >::domain().

◆ limits_

template<BacktrackingDomain Domain>

SearchLimits Aleph::Depth_First_Backtracking< Domain >::limits_

private

Definition at line 379 of file Backtracking.H.

Referenced by Aleph::Depth_First_Backtracking< Domain >::dfs(), Aleph::Depth_First_Backtracking< Domain >::dfs_visited(), Aleph::Depth_First_Backtracking< Domain >::expansion_limit_reached(), Aleph::Depth_First_Backtracking< Domain >::limits(), Aleph::Depth_First_Backtracking< Domain >::search(), Aleph::Depth_First_Backtracking< Domain >::search(), Aleph::Depth_First_Backtracking< Domain >::set_limits(), and Aleph::Depth_First_Backtracking< Domain >::stop_after_solution().

◆ policy_

template<BacktrackingDomain Domain>

ExplorationPolicy Aleph::Depth_First_Backtracking< Domain >::policy_

private

Definition at line 378 of file Backtracking.H.

Referenced by Aleph::Depth_First_Backtracking< Domain >::policy(), Aleph::Depth_First_Backtracking< Domain >::search(), Aleph::Depth_First_Backtracking< Domain >::search(), Aleph::Depth_First_Backtracking< Domain >::set_policy(), and Aleph::Depth_First_Backtracking< Domain >::stop_after_solution().

◆ supports_best_first

template<BacktrackingDomain Domain>

constexpr bool Aleph::Depth_First_Backtracking< Domain >::supports_best_first = false

staticconstexpr

Compile-time marker: Depth_First_Backtracking only supports Depth_First strategy.

Passing ExplorationPolicy::Strategy::Best_First to this engine raises std::invalid_argument at runtime. Check this constant before constructing a policy to detect the mismatch at compile time.

Definition at line 108 of file Backtracking.H.

The documentation for this class was generated from the following file:

Backtracking.H

Public Types

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Domain_Type

◆ Move

◆ Result

◆ Solution

◆ Solution_Compare

◆ State

Constructor & Destructor Documentation

◆ Depth_First_Backtracking()

Member Function Documentation

◆ dfs()

◆ dfs_visited()

◆ domain() [1/2]

◆ domain() [2/2]

◆ expansion_limit_reached()

◆ limits()

◆ policy()

◆ search() [1/5]

◆ search() [2/5]

◆ search() [3/5]

◆ search() [4/5]

◆ search() [5/5]

◆ set_limits()

◆ set_policy()

◆ stop_after_solution()

Member Data Documentation

◆ compare_

◆ domain_

◆ limits_

◆ policy_

◆ supports_best_first