Every Square Once: Hamiltonian Paths in Flight Planning

Picture this: you’re planning a grid survey flight over farmland, needing to photograph every square kilometre exactly once without retracing your path. Fuel is expensive, time is limited, and you can’t afford to miss a section or waste fuel covering the same ground twice. This is the essence of a Hamiltonian path—a route through a graph that visits every vertex exactly once.

Unlike Eulerian paths (which traverse every edge), Hamiltonian paths care about visiting every location. In chess, the knight’s tour is a famous Hamiltonian path where the knight visits all 64 squares exactly once. In aviation, it’s the difference between checking every waypoint versus checking every flight corridor.

proc hamiltonian_exists {graph start} {
    set visited [dict create]
    set path [list $start]
    dict set visited $start 1
    return [ham_dfs $graph $start $visited $path [dict size $graph]]
}

proc ham_dfs {graph current visited path target_length} {
    if {[llength $path] == $target_length} {
        return $path
    }
    
    foreach neighbor [dict get $graph $current] {
        if {![dict exists $visited $neighbor]} {
            dict set visited $neighbor 1
            lappend path $neighbor
            set result [ham_dfs $graph $neighbor $visited $path $target_length]
            if {$result ne ""} { return $result }
            dict unset visited $neighbor
            set path [lrange $path 0 end-1]
        }
    }
    return ""
}

def hamiltonian_path(graph, start, visited=None, path=None):
    if visited is None:
        visited, path = set([start]), [start]
    
    if len(path) == len(graph):
        return path
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            visited.add(neighbor)
            result = hamiltonian_path(graph, neighbor, visited, path + [neighbor])
            if result:
                return result
            visited.remove(neighbor)
    
    return None

The brutal truth? Finding Hamiltonian paths is NP-complete—there’s no known polynomial-time algorithm. As your grid grows, the computation explodes exponentially. A 10×10 survey grid might take minutes to solve; a 20×20 could take years.

In practice, pilots use heuristics: fly rectangular patterns, follow prevailing winds, or use GPS waypoint optimization. Sometimes the mathematically perfect solution isn’t the one that gets you home before weather moves in.