When Routes Fail: Backtracking Through Sky and Code

You’re 2,000 feet above the Rockies when the clouds roll in. VFR means you need to see where you’re going, so you bank left, retracing your GPS track until you find clear sky. Later, printing that same track as a relief map, your slicer chokes on an overhang—time to backtrack through the settings until something works.

Backtracking is the art of systematic retreat. When your current path hits a dead end, you return to the last decision point and try something else. Prolog makes this elegant:

find_route(Start, End, [Start|Path]) :-
    connected(Start, Next),
    \+ member(Next, [Start|Path]),
    find_route(Next, End, [Next|Path]).
find_route(End, End, [End]).

connected(yvr, ycd). connected(ycd, cyyc).
connected(yvr, czst). connected(czst, cyyc).

Ask for find_route(yvr, cyyc, Route) and Prolog explores each path automatically. Hit turbulence at CZST? It backtracks to YVR and tries the YCD route instead. The \+ member constraint prevents circles—crucial when your fuel is finite.

Go takes a more explicit approach, manually managing the search stack:

func contains(path []string, node string) bool {
    for _, p := range path {
        if p == node {
            return true
        }
    }
    return false
}

func findRoute(graph map[string][]string, start, end string, path []string) []string {
    if start == end { return append(path, end) }
    for _, next := range graph[start] {
        if !contains(path, next) {
            if result := findRoute(graph, next, end, append(path, start)); result != nil {
                return result
            }
        }
    }
    return nil
}

Same logic, different philosophy. Prolog treats backtracking as the natural order of things—try, fail, try again. Go makes you think about the stack, the recursive calls, the explicit returns. Both get you home safely, but Go shows you every step of the navigation while Prolog just handles the flying.