Hamiltonian Cycle Backtracking

A Bit of History

The problem takes its name from Sir William Rowan Hamilton, who in 1857 invented the Icosian Game — a puzzle played on the edges of a dodecahedron, challenging players to find a cycle visiting all 20 vertices exactly once. Hamilton sold the rights to the game to a toy manufacturer, but it never achieved commercial success. It took over a century for the true computational difficulty to be understood: in 1972, Richard Karp's landmark paper "Reducibility Among Combinatorial Problems" proved Hamiltonian Cycle to be NP-complete — one of his original 21 NP-complete problems, cementing it as a canonical example of exponential worst-case difficulty in graph theory.

Working Principle: Backtracking with Pruning

The algorithm builds a candidate cycle incrementally, one vertex at a time, using recursive backtracking:

• Start the path at an arbitrary fixed vertex (WLOG, since any Hamiltonian cycle can be rotated to start anywhere).
• At each step, try extending the current path to each unvisited neighbor of the last vertex placed.
• Prune immediately if a candidate neighbor isn't actually adjacent to the last vertex in the graph — never even attempt an invalid extension.
• If all $V$ vertices have been placed, check whether the last vertex connects back to the start — if so, a Hamiltonian cycle is found.
• If a dead end is reached (no valid unvisited neighbor and not all vertices placed), backtrack: remove the last vertex and try the next candidate at the previous level.

Worked Example

A 5-vertex graph shaped like a pentagon with one diagonal: cycle edges 0-1, 1-2, 2-3, 3-4, 4-0, plus diagonal 0-2.

• Start path at vertex 0: [0].
• Try neighbor 1: [0, 1]. Try neighbor 2 (of 1): [0, 1, 2]. Try neighbor 3 (of 2): [0, 1, 2, 3]. Try neighbor 4 (of 3): [0, 1, 2, 3, 4]. All 5 vertices placed — check if 4 connects back to 0: yes! Hamiltonian cycle found: 0 → 1 → 2 → 3 → 4 → 0.

If the diagonal edge 0-2 didn't exist and the path had instead tried 0→2 early, it would dead-end and backtrack to try 0→1 next — exactly the recursive exploration described above.

Complexity Analysis

$$\text{Time (worst case): } O(V!) \qquad \text{Space: } O(V) \text{ for the recursion stack and visited array}$$

Pruning dramatically improves the practical running time on sparse or structured graphs — often finishing in milliseconds — but the theoretical worst case remains factorial, since no known polynomial-time algorithm exists (and none can exist unless P = NP, given the problem's NP-completeness).

Implementation

def hamiltonian_cycle(n, adj_matrix):
    """
    n: number of vertices
    adj_matrix: n x n boolean adjacency matrix
    Returns a Hamiltonian cycle as a list of vertices, or None if none exists.
    """
    path = [0]  # fix the starting vertex (WLOG)
    visited = [False] * n
    visited[0] = True

    def backtrack():
        if len(path) == n:
            # All vertices placed; check the closing edge back to start
            return adj_matrix[path[-1]][path[0]]

        last = path[-1]
        for candidate in range(n):
            if not visited[candidate] and adj_matrix[last][candidate]:
                path.append(candidate)
                visited[candidate] = True

                if backtrack():
                    return True

                # Backtrack: undo this choice
                path.pop()
                visited[candidate] = False

        return False

    if backtrack():
        return path
    return None

# Example: pentagon (0-1-2-3-4-0) plus diagonal 0-2
n = 5
adj = [[False] * n for _ in range(n)]
edges = [(0,1), (1,2), (2,3), (3,4), (4,0), (0,2)]
for u, v in edges:
    adj[u][v] = adj[v][u] = True

result = hamiltonian_cycle(n, adj)
print("Hamiltonian cycle:", result)

#include <iostream>
#include <vector>

using namespace std;

bool backtrack(int n, vector<vector<bool>>& adj, vector<int>& path, vector<bool>& visited) {
    if ((int)path.size() == n) {
        return adj[path.back()][path[0]];
    }

    int last = path.back();
    for (int candidate = 0; candidate < n; candidate++) {
        if (!visited[candidate] && adj[last][candidate]) {
            path.push_back(candidate);
            visited[candidate] = true;

            if (backtrack(n, adj, path, visited)) return true;

            path.pop_back();
            visited[candidate] = false;
        }
    }
    return false;
}

vector<int> hamiltonianCycle(int n, vector<vector<bool>>& adj) {
    vector<int> path = {0};
    vector<bool> visited(n, false);
    visited[0] = true;

    if (backtrack(n, adj, path, visited)) return path;
    return {};
}

int main() {
    int n = 5;
    vector<vector<bool>> adj(n, vector<bool>(n, false));
    vector<pair<int,int>> edges = {{0,1},{1,2},{2,3},{3,4},{4,0},{0,2}};
    for (auto& e : edges) {
        adj[e.first][e.second] = adj[e.second][e.first] = true;
    }

    vector<int> result = hamiltonianCycle(n, adj);
    cout << "Hamiltonian cycle: ";
    for (int v : result) cout << v << " ";
    cout << endl;
    return 0;
}

import java.util.*;

public class HamiltonianCycle {
    static boolean backtrack(int n, boolean[][] adj, List<Integer> path, boolean[] visited) {
        if (path.size() == n) {
            return adj[path.get(path.size() - 1)][path.get(0)];
        }

        int last = path.get(path.size() - 1);
        for (int candidate = 0; candidate < n; candidate++) {
            if (!visited[candidate] && adj[last][candidate]) {
                path.add(candidate);
                visited[candidate] = true;

                if (backtrack(n, adj, path, visited)) return true;

                path.remove(path.size() - 1);
                visited[candidate] = false;
            }
        }
        return false;
    }

    public static List<Integer> solve(int n, boolean[][] adj) {
        List<Integer> path = new ArrayList<>();
        path.add(0);
        boolean[] visited = new boolean[n];
        visited[0] = true;

        if (backtrack(n, adj, path, visited)) return path;
        return null;
    }

    public static void main(String[] args) {
        int n = 5;
        boolean[][] adj = new boolean[n][n];
        int[][] edges = {{0,1},{1,2},{2,3},{3,4},{4,0},{0,2}};
        for (int[] e : edges) {
            adj[e[0]][e[1]] = true;
            adj[e[1]][e[0]] = true;
        }

        List<Integer> result = solve(n, adj);
        System.out.println("Hamiltonian cycle: " + result);
    }
}

Real-World Applications

Exercises

1. Trace the backtracking algorithm on the Petersen graph (10 vertices, famously Hamiltonian-path-having but NOT Hamiltonian-cycle-having) and observe where every branch fails.
2. Add a degree-based pre-check: if any vertex has degree less than 2, immediately report "no Hamiltonian cycle exists" without searching.
3. Modify the algorithm to find a Hamiltonian path (not necessarily a cycle) by removing the closing-edge requirement.
4. Challenge: Implement Warnsdorff's heuristic (always move to the neighbor with the fewest onward options) to speed up practical performance, as used in Knight's Tour solvers.

Limitations