2.2.2 - Backtracking

Choose, explore and undo a failed branch

Backtracking explores possible choices and returns to an earlier decision when a branch cannot produce a valid solution. It then tries an untried alternative. Its repeated pattern is choose → explore → undo on failure. Undo restores the state before the choice; simply jumping to another branch while retaining failed choices can corrupt the solution.

Imagine directed passages between rooms. The permitted outgoing rooms are listed in this order:

Find a route from S to G without repeating a room in the current route. Start with [S], choose A then C, giving [S,A,C]. C's only next room is A, already in the route. This branch fails. Undo C to restore [S,A]; A has no other choice, so undo A to restore [S]. Try B, then G, giving [S,B,G] and success.

This is depth-first exploration: complete a branch before trying the next one. The trial order determines which solution is found first. Backtracking does not always begin at a leftmost node; it begins when the current branch has no usable continuation, or a completed choice fails a constraint. A successful result is not necessarily shortest or best.

Reject infeasible choices and stop safely

A feasibility check rejects a partial choice that already breaks a constraint. In the room problem, adding a room already in the route is infeasible. This cuts off a cycle before it becomes an unending sequence of calls. All permitted passages still need to be tried when earlier alternatives fail.

Distinguish success from exhaustion. Reaching the goal is a success base case. Having no permissible next room is failure for that branch, so return to the previous decision. Only after all choices at the start have failed can the algorithm report that no route exists under the stated rules.

For a finite graph with n rooms and no repeated room in a route, depth is at most n rooms. Finite choices and bounded depth make exploration terminate, although there can be very many possible routes. The path test here is local to the current route. Once a room has been undone, another branch may try it again; a permanent global ban would be a different design and needs its own correctness argument.

Feasibility is useful in other settings. While constructing a timetable, reject a lesson if its teacher is already busy in the proposed slot. When choosing non-negative weights to reach a target, a partial sum above the target can never be rescued by adding another non-negative weight. That pruning rule would be unsafe if negative weights were allowed: a later negative weight could reduce the sum. A bound is justified by the input contract, not just by having worked on one example.

Read and write a restoring search

A recursive helper can keep the current route while its call stack records the earlier decision points. Represent the graph as a dictionary mapping every room, including terminal rooms, to an ordered list of outgoing rooms. The inputs are finite and start and goal are graph keys. The result is the first simple route in this order, or None if no route is found.

def first_route(graph, start, goal):
    path = [start]

    def explore(room):
        if room == goal:
            return path.copy()
        for next_room in graph[room]:
            if next_room not in path:
                path.append(next_room)
                answer = explore(next_room)
                if answer is not None:
                    return answer
                path.pop()
        return None

    return explore(start)

append makes the choice; the recursive call explores it; pop removes the last chosen room after failure. A failed call has restored its own deeper choices before returning, so this pop removes exactly the choice made by its caller. The path remains a valid route at every call entry. On success, propagate the result immediately rather than continuing to try other branches.

The goal returns a copy of the route, preserving the successful result independently of mutable working state. With start == goal, the answer is [start] before any passage is followed. A disconnected goal returns None; this differs from an empty route. The algorithm does not modify the supplied graph. Incorrect node references violate its input contract rather than specifying a new meaning for a missing room.