Use a stack for depth-first search

Depth-first search expands the newest scheduled work first. A LIFO stack follows a branch before returning to older frontier work. It can find a route, but does not guarantee a route with the fewest edges.

We use an iterative stack and mark cells when pushed. Push legal neighbors in reverse order so the first direction in our documented order is popped next. This fixes our traversal deterministically. Because sibling cells can already be discovered on the stack, do not claim this parent tree is identical to every recursive DFS implementation.

A Python list is suitable as a stack: append and pop use its end. If you push up, right, down and left in that order, left comes off first. Reverse the neighbor list before pushing to make up the first available choice.

Discovery still happens when pushing. A cycle must not repeatedly reinsert known cells. First parents remain fixed even if another branch later encounters the same vertex.

frontier = ["older branch"]
for neighbor in reversed(["up", "right", "down"]):
    frontier.append(neighbor)
print(frontier.pop())
print(frontier)

On the fork fixture, the rightward branch goes around a wall before reaching the goal. The stack follows it even though a two-step route down from the start is waiting. The resulting path is valid and longer. That is evidence of DFS behavior, not a bug in path reconstruction.

The exported trace records the frontier, expansion sequence and discovery order after each expansion. Those are copied lists. If snapshots retained references to the live lists, the ready frame could silently turn into the final frame.

A textbook adjacency-list search runs in O(V+E) time with O(V) discovery storage. This bounded teaching lab additionally validates grid calls and copies growing trace snapshots. Those costs can make the full exported run O(V²) in time and trace storage. The 16 × 16 limit keeps it inspectable; for larger graphs, validate once and stream small events instead.

parents = {"start":None}
for current, other in [("start","A"),("start","B"),("B","A")]:
    if other not in parents:
        parents[other] = current
print(parents)

Complete the search and inspect the ready, expansion and done snapshots. A one-cell start/goal should expand once; an isolated start with a different goal should exhaust its frontier. Check every non-root parent is an actual legal neighbor and every expanded cell appears only once.

The next path lesson follows these parent links. It does not infer a route by drawing lines through the expansion sequence.