--- title: 'Hamiltonian Paths' source: 'https://academia.sh/en/courses/advanced-algorithms/hamiltonian-paths' course: 'Advanced Algorithms and Problem Solving' language: en updated: '2026-08-17T18:07:23+00:00' license: 'CC BY-SA 4.0' --- # Hamiltonian Paths Framing an existence question as a decision problem and counting decision, search, counting, and verification separately: a path exists on 25 of 40 graphs, and deciding spends 1526 steps while counting spends 29,270, a ratio of 19.18. On all 15 graphs where no path exists, the decision step count is exactly equal to the counting step count, both 2538. The second pool gives the same structure, with 23 and 17 graphs. Verifying a found path takes 7 steps per graph, searching for one takes an average of 61. The names of complexity classes are left to the Theory of Computation course. The last row of the knight's tour opened a distinction: on the four-by-four board there was no tour, and both orderings visited exactly the same number of nodes. A yes answer could become cheap; a no answer could not. This lesson makes that distinction the topic's central question. A Hamiltonian path is a path that **passes through every node of a graph exactly once**. The knight's tour is a special case of this: squares are nodes, knight moves are edges. The question here is no longer "which is best" but **"does one exist."** This is a **decision problem**, and its answer is a single word. Two more questions stand alongside it: the **search** problem asks for a path, the **counting** problem asks how many there are. All three questions look at the same input, and the cost of all three is measured separately. - **CP50.** Graphs come from the shared definition's generator: 8 nodes, each pair of nodes connected with a 38 percent share, undirected. Seed **20260218**, second pool **20260219**, 40 graphs per pool. - **CP51.** **The decision problem:** does a path passing through every node exist. The procedure halts as soon as it finds the first path; if none exists, it scans the entire search space. - **CP52.** **The search problem:** if such a path exists, **which one**. In this lesson, the decision procedure already produces the path; the step count of search and decision are **the same** for this problem, and this is a measured result, not a general rule. - **CP53.** **The counting problem:** how many are there. The procedure never halts; it scans the entire space. Since every path is traversed from both ends, the count includes every path twice; what is measured is **steps**, not the count itself. - **CP54.** **Verification:** whether a given candidate path is genuinely a Hamiltonian path is tested. A step is checking whether two consecutive nodes are adjacent. - **CP55.** The oracle is the counting procedure: it scans the space completely, so its answer is correct by definition. The decision's answer is compared against the oracle's count on every graph. - **CP56.** The measure is **steps**; a step is a node visit in the search tree. - **CP57.** Yes graphs and no graphs are **totaled separately**. Combining them into a single average would erase the difference this lesson measures. - **CP58.** **The names of complexity classes are not written in this lesson.** How the difference between verification and search is named belongs to the Theory of Computation course. - **CP59.** The cheap test checks only **necessary conditions**. Its wrong-answer count is measured against the oracle; coming out zero is not assumed, it is counted. ## Three Questions, One Input The block below runs decision and counting separately on every graph, verifies any path found, and totals the results separately for yes and no graphs. ```python SEED = 20260218 N = 8 def generator(seed): d = seed def next_val(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_val def graphs(seed=SEED, samples=40, share=38, n=N): """Undirected graph: each pair connected with probability `share` percent.""" r = generator(seed) pool = [] for _ in range(samples): neighbors = {i: set() for i in range(n)} for i in range(n): for j in range(i + 1, n): if r(100) < share: neighbors[i].add(j) neighbors[j].add(i) pool.append(neighbors) return pool class Counter: def __init__(self): self.steps = 0 def count(self): self.steps += 1 def search(neighbors, s, stop, n=N): """stop=True: halts at the first Hamiltonian path. stop=False: counts them all.""" found, count = [], 0 def walk(v, path): nonlocal count s.count() if len(path) == n: count += 1 if not found: found.append(tuple(path)) return True for k in sorted(neighbors[v]): if k not in path: path.append(k) done = walk(k, path) path.pop() if done and stop: return True return False for start in range(n): if walk(start, [start]) and stop: break return (found[0] if found else None), count def verify(neighbors, path, n=N): """Oracle: does the candidate path have n nodes, are consecutive pairs adjacent.""" steps = 0 if path is None or len(set(path)) != n: return False, steps for a, b in zip(path, path[1:]): steps += 1 if b not in neighbors[a]: return False, steps return True, steps for seed in (20260218, 20260219): yes = {"n": 0, "decision": 0, "counting": 0, "verification": 0} no = {"n": 0, "decision": 0, "counting": 0} equal = 0 for neighbors in graphs(seed): s1, s2 = Counter(), Counter() path, _ = search(neighbors, s1, True) _, count = search(neighbors, s2, False) if path is not None: ok, d = verify(neighbors, path) yes["n"] += 1 yes["decision"] += s1.steps yes["counting"] += s2.steps yes["verification"] += d else: no["n"] += 1 no["decision"] += s1.steps no["counting"] += s2.steps if s1.steps == s2.steps: equal += 1 print("seed", seed) print(" yes ", yes, "ratio", round(yes["counting"] / yes["decision"], 2)) print(" no ", no, "graphs with decision=counting:", equal, "/", no["n"]) ``` ``` seed 20260218 yes {'n': 25, 'decision': 1526, 'counting': 29270, 'verification': 175} ratio 19.18 no {'n': 15, 'decision': 2538, 'counting': 2538} graphs with decision=counting: 15 / 15 seed 20260219 yes {'n': 23, 'decision': 915, 'counting': 26792, 'verification': 161} ratio 29.28 no {'n': 17, 'decision': 4390, 'counting': 4390} graphs with decision=counting: 17 / 17 ``` ## Why a No Answer Accepts No Discount On the first pool, a path exists on **25 of 40 graphs**, and none on 15. On the yes graphs, decision spends a total of **1526 steps**, counting **29,270 steps**; a ratio of **19.18**. The decision procedure halts the moment it finds the first path and never enters the rest of the space. On no graphs, the two numbers are **identical**: 2538 and 2538. Moreover, this equality does not just hold in total — it holds **individually on all 15 of the 15 graphs**. The reason is not procedural but logical. To say "no," the decision procedure must see that not a single branch gives a path; if even one branch remains unseen, its answer is a guess. When there is no path, no early-stopping point ever arises, so the decision procedure traverses exactly the tree the counting procedure traverses. The second pool gives the same structure: 23 yes, 17 no, ratio 29.28, and the decision step count equals the counting step count on **17 of the 17** no graphs. The ratio on yes graphs rises from 19.18 to 29.28, meaning **the size of the ratio depends on the pool**; but the exact equality on no graphs holds **without exception** on both pools. One is a measured value; the other is a consequence of the procedure's structure, and the two are not written in the same sentence. This lets the previous lesson's knight's-tour row be reread. Both orderings visiting 29,976 nodes on the four-by-four board was not a coincidence: because the answer was no, there was no early-stopping point, and ordering could only have paid off by pulling that stop earlier. ## A Cheap Test That Works One Way A no answer being expensive does not mean **every** no answer is expensive. On some graphs, the absence of a path can be seen without entering the search at all: if the graph is disconnected, no path can reach every node, and if more than two nodes have only a single neighbor, they cannot all be an endpoint of the path. These are **necessary conditions**: if unmet, there is no path; if met, they say nothing. ```python from collections import deque SEED, N = 20260218, 8 def generator(seed): d = seed def next_val(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_val def graphs(seed=SEED, samples=40, share=38, n=N): r = generator(seed) pool = [] for _ in range(samples): neighbors = {i: set() for i in range(n)} for i in range(n): for j in range(i + 1, n): if r(100) < share: neighbors[i].add(j) neighbors[j].add(i) pool.append(neighbors) return pool class Counter: def __init__(self): self.steps = 0 def count(self): self.steps += 1 def cheap_test(neighbors, s, n=N): """Tests necessary conditions. Can say 'no'; cannot say 'yes'.""" queue, seen = deque([0]), {0} while queue: v = queue.popleft() for k in neighbors[v]: s.count() if k not in seen: seen.add(k) queue.append(k) if len(seen) < n: return "no" lone = 0 for v in range(n): s.count() if len(neighbors[v]) <= 1: lone += 1 return "no" if lone > 2 else "unknown" def decide(neighbors, s, n=N): def walk(v, path): s.count() if len(path) == n: return True for k in sorted(neighbors[v]): if k not in path: path.append(k) if walk(k, path): return True path.pop() return False return any(walk(start, [start]) for start in range(n)) for seed in (20260218, 20260219): cheap_no, cheap_steps, wrong = 0, 0, 0 remaining_no, remaining_steps = 0, 0 for neighbors in graphs(seed): s1, s2 = Counter(), Counter() y = cheap_test(neighbors, s1) exists = decide(neighbors, s2) cheap_steps += s1.steps if y == "no": cheap_no += 1 if exists: wrong += 1 elif not exists: remaining_no += 1 remaining_steps += s2.steps print("seed", seed, "| cheap test said 'no':", cheap_no, "| wrong:", wrong, "| cheap total steps:", cheap_steps) print(" no graphs the cheap test could not resolve:", remaining_no, "| full-scan steps:", remaining_steps) ``` ``` seed 20260218 | cheap test said 'no': 11 | wrong: 0 | cheap total steps: 1092 no graphs the cheap test could not resolve: 4 | full-scan steps: 676 seed 20260219 | cheap test said 'no': 13 | wrong: 0 | cheap total steps: 1102 no graphs the cheap test could not resolve: 4 | full-scan steps: 1638 ``` On the first pool, **11 of the 15** no graphs are resolved by the cheap test, with **zero wrong answers**: the test never says "no" to a graph that has a path. 4 graphs remain, and for those a full scan is unavoidable, 676 steps. On the second pool, 13 of the 17 no graphs are resolved, again zero wrong, again 4 graphs remaining, this time at 1638 steps. The 1092 steps the test spends across all forty graphs is below the 2538 steps a full scan spends on no graphs. But the entire saving is **one-directional**. The test can never say "yes" on any graph; of the 29 graphs it calls "unknown," 25 have a path and 4 do not, and telling the two apart again requires a full scan. A cheap proof always works in one direction, and its number cannot be read without saying which direction that is. ## Searching Versus Verifying The fourth number is verification. On yes graphs, the total is **175 steps**, that is, 7 steps per graph: seven consecutive pairs in an eight-node path. On the same graphs, **finding** the path spends an average of 61 steps, 8.7 times verification. The gap between these two numbers is small on a single graph in this lesson, but **what the two numbers do with scale** is not the same. Verification is node-count-minus-one steps and grows linearly with node count. Search's step count, on the other hand, depends on the size of the tree traversed. The block below sweeps node count and places the two growths side by side. ```python SEED = 20260218 def generator(seed): d = seed def next_val(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_val def graphs(n, share, seed=SEED, samples=20): r = generator(seed) pool = [] for _ in range(samples): neighbors = {i: set() for i in range(n)} for i in range(n): for j in range(i + 1, n): if r(100) < share: neighbors[i].add(j) neighbors[j].add(i) pool.append(neighbors) return pool class Counter: def __init__(self): self.steps = 0 def count(self): self.steps += 1 def decide(neighbors, n, s): """Halts at the first Hamiltonian path; if none exists, the whole space is scanned.""" found = [] def walk(v, path): s.count() if len(path) == n: found.append(tuple(path)) return True for k in sorted(neighbors[v]): if k not in path: path.append(k) done = walk(k, path) path.pop() if done: return True return False for start in range(n): if walk(start, [start]): return found[0] return None print(" n | yes | yes avg steps | no avg steps | verification steps") for n, share in ((6, 30), (8, 30), (10, 30), (12, 30)): e = h = ea = ha = 0 for neighbors in graphs(n, share): s = Counter() y = decide(neighbors, n, s) if y is None: h, ha = h + 1, ha + s.steps else: e, ea = e + 1, ea + s.steps print(f"{n:2d} | {e:4d} | {(ea // e if e else 0):18d} |" f" {(ha // h if h else 0):19d} | {n - 1:15d}") ``` ``` n | yes | yes avg steps | no avg steps | verification steps 6 | 2 | 8 | 23 | 5 8 | 6 | 121 | 92 | 7 10 | 9 | 164 | 757 | 9 12 | 10 | 1054 | 11601 | 11 ``` The three columns show three different kinds of growth. Verification is 5, 7, 9, 11: increasing by one with node count. On yes graphs, decision is 8, 121, 164, 1054. On no graphs, decision is 23, 92, 757, **11,601**; going from six nodes to twelve, it grows by more than five hundred times. At the eight-node row, the no average falls below the yes average; this single-row reversal comes from the scarcity of no graphs in that pool and does not generalize. What is measured is this: **verifying an answer and finding it are not the same order of magnitude**, and the gap widens with node count. At twelve nodes, testing a candidate path is 11 steps; showing that no such path exists averages 11,601 steps. The same graph, the same question, a thousandfold difference. ## Where the Naming Belongs Four numbers have been measured so far: decision, search, counting, verification. One thing remains unmeasured, and it is left out on purpose. Problems that appear cheap to verify but expensive to find have a **shared name**; there is a procedure for transforming these problems into one another, and a theory of the difference between "appears expensive" and "is expensive." None of this is built in this course. In the travelling salesman lesson, the "why is it hard" question was referred to the Theory of Computation course; the naming question here goes to the same place. What this course does is measure the **difference that course will speak about** and put it on the table: 11 steps against 11,601 steps, and that this is an observation, not a proof. This distinction leaves behind a useful habit. Before calling a problem hard, it must be written **which question** of that problem is expensive. For the same set of graphs, decision spent 1526 steps, counting 29,270, verification 175. The sentence "the Hamiltonian path is expensive" says nothing unless it states which of these three numbers it means. ## Summary - An existence question is framed as a decision problem; search and counting problems stand alongside it, and all three costs are measured separately on the same input. - On the 25 graphs where a path is found, decision spends 1526 steps, counting 29,270; the ratio is 19.18, and 29.28 on the second pool, meaning the size of the ratio depends on the pool. - On **every** graph where no path is found, decision steps exactly equal counting steps: 15 of 15 on the first pool, 17 of 17 on the second. A no answer leaves no early-stopping point. - Verification is 7 steps per graph, search averages 61; when node count is swept, verification rises one at a time while the cost of a no answer climbs from 23 to 11,601. - This measured difference is an observation; naming and proving it belongs to the Theory of Computation course and is not done in this lesson. ## Next Step The Classical Problems topic followed the same procedure across six problems: build the oracle, measure the pattern, count the split inputs. The next topic makes this procedure independent of the problem. Practice Discipline turns inferring which pattern fits a problem's step budget from its constraints, and comparing a solution against an oracle, into a habit. The first question is: given an input size, how is which pattern fits the budget found **by counting**, rather than guessed.