Hamiltonian Paths

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.

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.

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.

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.