Handle cycles, unreachable goals and deterministic ties

Not finding a path can be the correct answer. A blocked endpoint is an invalid request in our API. An open endpoint separated from the start by walls is a valid request whose result is unreachable.

The wrapper selects BFS or DFS, preserves its trace evidence and reconstructs only when the search actually found the goal. No retry removes walls or introduces diagonal moves. Keeping geometry fixed makes the result honest.

Cycles are normal in grids. The discovered guard is what makes them finite: every cell enters the frontier at most once. When the frontier becomes empty without expanding the goal, no reachable walkable cell remains unexplored.

Repeating an input should reproduce its parents, expansions and route. Use ordered neighbor lists and parent insertion order. A set is useful for membership; do not iterate it to decide the next move.

parents = {"S":None}
frontier = ["S"]
for current, other in [("S","A"),("A","S"),("A","B"),("B","A")]:
    if other not in parents:
        parents[other] = current
        frontier.append(other)
print("scheduled once", frontier)
print("parents", parents)

The wrapper’s output has both status and evidence. A found result has a route with the requested endpoints. An unreachable result has an empty route, an exhausted frontier and the actual expanded cells. Both can be animated usefully.

Test a one-cell board, open rows and columns, a cycle, an isolated goal and the fork where BFS and DFS differ. On an open rectangle, Manhattan distance gives an independent BFS oracle: from top-left to bottom-right the shortest edge count is height + width − 2. That tests the guarantee without copying the implementation into the test.

This is not Dijkstra’s algorithm. If movement has different costs, minimum edge count may not minimize total cost. Do not add terrain weights while keeping a shortest-cost claim for the same FIFO search.

for height,width in [(1,5),(5,1),(4,4)]:
    minimum_moves = height + width - 2
    print((height,width), "open-grid BFS distance", minimum_moves)

Complete the wrapper and prove it honors both algorithm choices. Use the fork fixture to check different valid route lengths rather than assuming every example should produce the same path.

Next we export the trace as plain JSON data and replay it with step, pause and reset controls. That boundary will keep the visualizer independent from Python execution.