Hamiltonian-path search
/ ham-il-TOH-nee-an /
Suppose a delivery driver must visit every address in a neighborhood exactly once, traveling only along the existing roads. A route that touches each location once and never repeats one is a Hamiltonian path; if it also returns to where it began, it is a Hamiltonian cycle. The search problem asks whether such a path (or cycle) exists in a given graph, and if so, to find one.
Backtracking builds the path one vertex at a time. Start from some vertex and mark it visited. At each step, you stand at a current vertex and look at its neighbors; for each neighbor not yet visited, move there (extend the path), mark it, recurse to continue, and on return unmark it to free it for other routes. The natural pruning is simply you may only step to an unvisited vertex that is adjacent to where you stand. The path is complete and a solution when all n vertices have been visited (for a cycle, additionally require an edge back to the start). The state-space tree branches on which unvisited neighbor to go to next; in the worst case its size is on the order of n! because a path is an ordering of the vertices, but the adjacency constraint and the visited-mark prune away every step into a dead end or a repeat.
Hamiltonian path and cycle are famously NP-complete (this is the heart of why the traveling salesman problem is hard), so there is no known algorithm that solves all instances quickly, and the backtracking search is exponential in the worst case — a stark contrast with the Eulerian path (visit every edge once), which has an easy linear-time test. The contrast is the lesson: a tiny change in the question (every vertex once vs. every edge once) flips a problem from trivially easy to NP-complete. For moderate n, dynamic programming over subsets (Held-Karp, O(2^n n^2)) beats naive backtracking, but for large n you fall back on heuristics and bounds.
In a square graph with vertices 1-2-3-4 and edges 1-2, 2-3, 3-4, 4-1, search from 1: go 1 -> 2 -> 3 -> 4, all four visited, done — that is a Hamiltonian path (and since 4-1 is an edge, also a cycle). Add a fifth vertex 5 joined only to 1: now no Hamiltonian path through all five from 1 can end at 5 unless 5 is an endpoint, and backtracking discovers this by exhausting the dead ends.
Extend the path only to unvisited adjacent vertices; a full visit of all n vertices is a solution, dead ends backtrack.
Hamiltonian (every vertex once) is NP-complete, but Eulerian (every edge once) is easy — a graph has an Eulerian path exactly when it is connected with at most two odd-degree vertices. The similar wording hides a vast gap in difficulty.