Depth-First Search
Many kinds of problems can be solved by search, which involves finding a goal from a starting state by applying operators that lead to a new state.
Depth-first search ( DFS) follows an implicit tree of size O(bdepth), where b is the branching factor. (number of children of a node). Given a state, we test whether it is a goal or a terminal failure node; if not, we generate successor states and try searching from each of them. Many of these searches may fail, and we will backtrack and try a different branch.