3.1. qlinks.solver.deep_first_search

Classes

DeepFirstSearch(start_state[, max_steps])	Deep first search (DFS) algorithm.
Node(*args, **kwargs)

class qlinks.solver.deep_first_search.Node(*args, **kwargs)

Bases: Protocol

extend_node()

Return type:

Set[Self]

is_the_solution()

Return type:

bool

__init__(*args, **kwargs)

class qlinks.solver.deep_first_search.DeepFirstSearch(start_state, max_steps=50000)

Bases: Generic[AnyNode]

Deep first search (DFS) algorithm.

Parameters:

• start_state (AnyNode) – The initial state as the first Node.

• max_steps (int) – The maximum number of steps for deep first search, default 50000.

frontier

A set of Node to be determined.

Type:

Set[qlinks.solver.deep_first_search.AnyNode]

n_checked_nodes

The number of checked nodes.

Type:

int

selected_nodes

A list of Node representing candidate solutions.

Type:

List[qlinks.solver.deep_first_search.AnyNode]

Examples

If Node has been implemented, the algorithm can be launched through

>>> init_state: AnyNode = Node()  # replace with any derived child class from Node
>>> dfs = DeepFirstSearch(init_state)
>>> selected_states: List[AnyNode] = dfs.solve()

Notes

For general purpose, users must implement all abstractive methods in Node.

References

https://python.plainenglish.io/solve-sudoku-using-depth-first-search-algorithm-dfs-in-python-2be3caa08ccd

start_state: AnyNode

max_steps: int

frontier: Set[AnyNode]

n_checked_nodes: int

selected_nodes: List[AnyNode]

property frontier_is_empty: bool

solve(n_solution=1, progress=False)

Search for the solutions.

Parameters:

• n_solution (int) – Desired number of solutions. Default 1. In practical usage, it’s normally

• scenario (difficult to know all possible solutions in prior. In that)

• be (n_solution can)

• number (just set as a large)

• when (will automatically stop after it walked through the entire configuration space (or)

• max_steps). (it has exceeded)

• progress (bool) – Whether to show the progress bar. Default True.

Returns:

A Node or a list of Node which fulfills is_the_solution().

Raises:

StopIteration – if no solution can be found or the number of iteration exceeds max_steps.

Return type:

List[AnyNode]

__init__(start_state, max_steps=50000)

Parameters:

• start_state (AnyNode)

• max_steps (int)

Return type:

None