backtrack search
a graph search strategy that considers states in a graph recursively. If the present state is not the goal state, then its first child (node) is examined. If this child is not the goal state, then its first child is taken. If there are no children of a state, then the next sibling of the present state is considered. If there are no further siblings of a state, then the sibling of the state’s parent has to be considered. This process continues until either a goal state is found or there are no further states to examine. States, their siblings, and their children are usually (but not necessarily) considered in a left-to-right format.