Uninformed Search

Many puzzles are search problems in disguise: a set of states, a start, a goal, and moves between states. Solving one means finding a path through the implicit graph of states without ever building it in full. This project applies breadth-first search and depth-first search to the chickens-and-foxes river crossing.

A state records how many chickens and foxes sit on each bank and which side the boat is on. A move ferries one or two animals across, and a state is legal only when foxes never outnumber chickens on a bank that still has chickens. The start has everyone on one side; the goal has everyone on the other. Nothing enumerates the graph ahead of time — successors are generated on demand from each state.

BFS and DFS differ only in which frontier state they expand next: BFS uses a queue, DFS a stack, and that single choice sets their behavior. BFS explores by distance from the start, so the first time it reaches the goal it has found a path with the fewest crossings; DFS dives down one branch before backtracking, using less memory but returning whatever path it reaches first. A visited set keeps both from re-expanding a state and looping on the graph's cycles.

A queue for the frontier gives BFS, a stack gives DFS — the rest of the procedure is identical.

The two diverge in what they guarantee. Let $b$ be the branching factor, $d$ the depth of the shallowest goal, and $m$ the depth of the deepest state. BFS is complete (with finite $b$ it always finds a goal when one exists) and optimal when every move costs the same, since it reaches goals in order of depth. Its price is memory: it holds an entire frontier level at once, so time and space are both $O(b^d)$, and the space bound is what breaks it first on a wide graph. DFS keeps only the current path and its unexpanded siblings, $O(bm)$ space, but it is not optimal — it returns the first path it stumbles onto — and without the visited set it would not even be complete on a cyclic graph, looping forever down one branch.

Iterative deepening is the compromise. Run depth-limited DFS with limits $1,2,3,\dots$, restarting from scratch each time, until a goal appears. It inherits DFS's $O(bd)$ memory and BFS's completeness and optimality. Re-searching the shallow levels sounds wasteful, but the bottom level of a branching tree dwarfs everything above it, so the repeated work is a constant factor and the total stays $O(b^d)$ — BFS's guarantees at DFS's footprint.