Depth-first search (DFS) explores one branch as deeply as possible, then backtracks to the latest decision point and tries another branch. It is a blind graph-search method: it uses no information about the search space and stops when it finds a destination or exhausts the paths. section 3.2 section 3.6
A stack drives the search:
- Initialize a last-in, first-out stack with the source node, an empty explored collection, and an unsuccessful-found state. section 3.3.2
- Pop the newest node, mark it explored, and expand its successors. section 3.3.2
- Prefer DFS when the graph is wide, adjacent nodes are numerous, and no path is excessively deep; avoid it when a shallow solution is likely in a very deep graph. section 3.3.2
Solving an 8-puzzle
DFS can search an 8-puzzle by treating blank-tile moves as successors. With a depth bound of five, dead ends become terminal nodes and the search backtracks to earlier alternatives. A Python run reports process time, memory, explored states, and solution steps. section 3.3.2
