1070 Advanced

1070-hamiltonian-path — Hamiltonian Path

Functional Programming

Tutorial

The Problem

A Hamiltonian path visits every vertex of a graph exactly once. Unlike Euler paths (which traverse every edge once), Hamiltonian paths are NP-complete — no polynomial algorithm is known. The Traveling Salesman Problem (TSP) is a weighted Hamiltonian path problem and is one of the most famous NP-hard problems in computer science.

The backtracking approach tries to extend the path one vertex at a time, backtracking when a dead end is reached. For small graphs (up to ~20 vertices), this is practical.

🎯 Learning Outcomes

• Implement Hamiltonian path finding via backtracking

• Use a visited array to enforce the "exactly once" constraint

• Understand why Hamiltonian path is NP-complete

• Contrast with Eulerian path (polynomial time via Hierholzer's algorithm)

• Connect to TSP and its approximation algorithms

Code Example

#![allow(clippy::all)]
// 1070: Hamiltonian Path — Backtracking

// Approach 1: Adjacency matrix backtracking (fixed start = 0)
fn hamiltonian_path(adj: &[Vec<i32>]) -> Option<Vec<usize>> {
    let n = adj.len();
    let mut path = vec![0usize; n];
    let mut visited = vec![false; n];
    path[0] = 0;
    visited[0] = true;

    fn solve(pos: usize, adj: &[Vec<i32>], path: &mut Vec<usize>, visited: &mut Vec<bool>) -> bool {
        let n = adj.len();
        if pos == n {
            return true;
        }
        for v in 0..n {
            if !visited[v] && adj[path[pos - 1]][v] == 1 {
                path[pos] = v;
                visited[v] = true;
                if solve(pos + 1, adj, path, visited) {
                    return true;
                }
                visited[v] = false;
            }
        }
        false
    }

    if solve(1, adj, &mut path, &mut visited) {
        Some(path)
    } else {
        None
    }
}

// Approach 2: Try all starting vertices
fn hamiltonian_path_any(adj: &[Vec<i32>]) -> Option<Vec<usize>> {
    let n = adj.len();
    for start in 0..n {
        let mut path = vec![0usize; n];
        let mut visited = vec![false; n];
        path[0] = start;
        visited[start] = true;

        fn solve(
            pos: usize,
            adj: &[Vec<i32>],
            path: &mut Vec<usize>,
            visited: &mut Vec<bool>,
        ) -> bool {
            let n = adj.len();
            if pos == n {
                return true;
            }
            for v in 0..n {
                if !visited[v] && adj[path[pos - 1]][v] == 1 {
                    path[pos] = v;
                    visited[v] = true;
                    if solve(pos + 1, adj, path, visited) {
                        return true;
                    }
                    visited[v] = false;
                }
            }
            false
        }

        if solve(1, adj, &mut path, &mut visited) {
            return Some(path);
        }
    }
    None
}

// Approach 3: Bitmask DP for Hamiltonian path existence (O(2^n * n^2))
fn hamiltonian_exists_dp(adj: &[Vec<i32>]) -> bool {
    let n = adj.len();
    if n == 0 {
        return true;
    }
    // dp[mask][i] = can we reach node i having visited exactly the nodes in mask?
    let mut dp = vec![vec![false; n]; 1 << n];
    for i in 0..n {
        dp[1 << i][i] = true;
    }
    for mask in 1..(1 << n) {
        for u in 0..n {
            if !dp[mask][u] {
                continue;
            }
            if mask & (1 << u) == 0 {
                continue;
            }
            for v in 0..n {
                if mask & (1 << v) == 0 && adj[u][v] == 1 {
                    dp[mask | (1 << v)][v] = true;
                }
            }
        }
    }
    let full = (1 << n) - 1;
    (0..n).any(|i| dp[full][i])
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_complete_graph() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 1],
            vec![1, 1, 0, 1],
            vec![1, 1, 1, 0],
        ];
        let path = hamiltonian_path(&adj).unwrap();
        assert_eq!(path.len(), 4);
    }

    #[test]
    fn test_path_graph() {
        let adj = vec![
            vec![0, 1, 0, 0],
            vec![1, 0, 1, 0],
            vec![0, 1, 0, 1],
            vec![0, 0, 1, 0],
        ];
        let path = hamiltonian_path(&adj).unwrap();
        assert_eq!(path.len(), 4);
    }

    #[test]
    fn test_any_start() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 1],
            vec![1, 1, 0, 1],
            vec![1, 1, 1, 0],
        ];
        assert!(hamiltonian_path_any(&adj).is_some());
    }

    #[test]
    fn test_bitmask_dp() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 1],
            vec![1, 1, 0, 1],
            vec![1, 1, 1, 0],
        ];
        assert!(hamiltonian_exists_dp(&adj));

        // Disconnected graph
        let adj2 = vec![vec![0, 0, 0], vec![0, 0, 0], vec![0, 0, 0]];
        assert!(!hamiltonian_exists_dp(&adj2));
    }
}

(* 1070: Hamiltonian Path — Backtracking *)

(* Approach 1: Adjacency matrix backtracking *)
let hamiltonian_path adj =
  let n = Array.length adj in
  let path = Array.make n (-1) in
  let visited = Array.make n false in
  path.(0) <- 0;
  visited.(0) <- true;
  let rec solve pos =
    if pos = n then true
    else begin
      let found = ref false in
      for v = 0 to n - 1 do
        if not !found && not visited.(v) && adj.(path.(pos - 1)).(v) = 1 then begin
          path.(pos) <- v;
          visited.(v) <- true;
          if solve (pos + 1) then found := true
          else begin
            path.(pos) <- -1;
            visited.(v) <- false
          end
        end
      done;
      !found
    end
  in
  if solve 1 then Some (Array.to_list path) else None

(* Approach 2: Adjacency list *)
let hamiltonian_path_adj adj n =
  let path = Array.make n (-1) in
  let visited = Array.make n false in
  path.(0) <- 0;
  visited.(0) <- true;
  let rec solve pos =
    if pos = n then true
    else begin
      let found = ref false in
      List.iter (fun v ->
        if not !found && not visited.(v) then begin
          path.(pos) <- v;
          visited.(v) <- true;
          if solve (pos + 1) then found := true
          else begin
            path.(pos) <- -1;
            visited.(v) <- false
          end
        end
      ) adj.(path.(pos - 1));
      !found
    end
  in
  if solve 1 then Some (Array.to_list path) else None

(* Approach 3: Try all starting vertices *)
let hamiltonian_path_any adj =
  let n = Array.length adj in
  let path = Array.make n (-1) in
  let visited = Array.make n false in
  let rec solve pos =
    if pos = n then true
    else begin
      let found = ref false in
      for v = 0 to n - 1 do
        if not !found && not visited.(v) && adj.(path.(pos - 1)).(v) = 1 then begin
          path.(pos) <- v;
          visited.(v) <- true;
          if solve (pos + 1) then found := true
          else begin
            path.(pos) <- -1;
            visited.(v) <- false
          end
        end
      done;
      !found
    end
  in
  let result = ref None in
  for start = 0 to n - 1 do
    if !result = None then begin
      Array.fill path 0 n (-1);
      Array.fill visited 0 n false;
      path.(0) <- start;
      visited.(start) <- true;
      if solve 1 then result := Some (Array.to_list path)
    end
  done;
  !result

let () =
  (* Complete graph K4 — trivially has Hamiltonian path *)
  let adj = [|
    [|0;1;1;1|];
    [|1;0;1;1|];
    [|1;1;0;1|];
    [|1;1;1;0|]
  |] in
  (match hamiltonian_path adj with
   | Some path -> assert (List.length path = 4)
   | None -> assert false);

  (* Path graph: 0-1-2-3 *)
  let adj2 = [|
    [|0;1;0;0|];
    [|1;0;1;0|];
    [|0;1;0;1|];
    [|0;0;1;0|]
  |] in
  (match hamiltonian_path adj2 with
   | Some path -> assert (List.length path = 4)
   | None -> assert false);

  (match hamiltonian_path_any adj with
   | Some path -> assert (List.length path = 4)
   | None -> assert false);

  Printf.printf "✓ All tests passed\n"

Key Differences

Early exit: Rust's recursive approach returns true/false, naturally exiting; OCaml uses a ref to propagate success upward.

NP-completeness: Both implementations are exponential in the worst case — no polynomial alternative exists.

Bitmask DP: For graphs up to ~20 vertices, bitmask DP gives O(2^n × n^2) time and O(2^n × n) space — better than backtracking's O(n!).

TSP connection: Hamiltonian path + edge weights = TSP; the Held-Karp bitmask DP algorithm solves TSP in O(2^n × n^2).

OCaml Approach

let hamiltonian_path adj =
  let n = Array.length adj in
  let path = Array.make n 0 in
  let visited = Array.make n false in
  visited.(0) <- true;
  let rec solve pos =
    if pos = n then Some (Array.to_list path)
    else
      let result = ref None in
      for v = 0 to n - 1 do
        if !result = None && not visited.(v) && adj.(path.(pos-1)).(v) = 1 then begin
          path.(pos) <- v; visited.(v) <- true;
          result := solve (pos + 1);
          if !result = None then visited.(v) <- false
        end
      done;
      !result
  in
  solve 1

Structurally identical. OCaml's ref result manages early exit; Rust returns from the inner function.

Full Source

#![allow(clippy::all)]
// 1070: Hamiltonian Path — Backtracking

// Approach 1: Adjacency matrix backtracking (fixed start = 0)
fn hamiltonian_path(adj: &[Vec<i32>]) -> Option<Vec<usize>> {
    let n = adj.len();
    let mut path = vec![0usize; n];
    let mut visited = vec![false; n];
    path[0] = 0;
    visited[0] = true;

    fn solve(pos: usize, adj: &[Vec<i32>], path: &mut Vec<usize>, visited: &mut Vec<bool>) -> bool {
        let n = adj.len();
        if pos == n {
            return true;
        }
        for v in 0..n {
            if !visited[v] && adj[path[pos - 1]][v] == 1 {
                path[pos] = v;
                visited[v] = true;
                if solve(pos + 1, adj, path, visited) {
                    return true;
                }
                visited[v] = false;
            }
        }
        false
    }

    if solve(1, adj, &mut path, &mut visited) {
        Some(path)
    } else {
        None
    }
}

// Approach 2: Try all starting vertices
fn hamiltonian_path_any(adj: &[Vec<i32>]) -> Option<Vec<usize>> {
    let n = adj.len();
    for start in 0..n {
        let mut path = vec![0usize; n];
        let mut visited = vec![false; n];
        path[0] = start;
        visited[start] = true;

        fn solve(
            pos: usize,
            adj: &[Vec<i32>],
            path: &mut Vec<usize>,
            visited: &mut Vec<bool>,
        ) -> bool {
            let n = adj.len();
            if pos == n {
                return true;
            }
            for v in 0..n {
                if !visited[v] && adj[path[pos - 1]][v] == 1 {
                    path[pos] = v;
                    visited[v] = true;
                    if solve(pos + 1, adj, path, visited) {
                        return true;
                    }
                    visited[v] = false;
                }
            }
            false
        }

        if solve(1, adj, &mut path, &mut visited) {
            return Some(path);
        }
    }
    None
}

// Approach 3: Bitmask DP for Hamiltonian path existence (O(2^n * n^2))
fn hamiltonian_exists_dp(adj: &[Vec<i32>]) -> bool {
    let n = adj.len();
    if n == 0 {
        return true;
    }
    // dp[mask][i] = can we reach node i having visited exactly the nodes in mask?
    let mut dp = vec![vec![false; n]; 1 << n];
    for i in 0..n {
        dp[1 << i][i] = true;
    }
    for mask in 1..(1 << n) {
        for u in 0..n {
            if !dp[mask][u] {
                continue;
            }
            if mask & (1 << u) == 0 {
                continue;
            }
            for v in 0..n {
                if mask & (1 << v) == 0 && adj[u][v] == 1 {
                    dp[mask | (1 << v)][v] = true;
                }
            }
        }
    }
    let full = (1 << n) - 1;
    (0..n).any(|i| dp[full][i])
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_complete_graph() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 1],
            vec![1, 1, 0, 1],
            vec![1, 1, 1, 0],
        ];
        let path = hamiltonian_path(&adj).unwrap();
        assert_eq!(path.len(), 4);
    }

    #[test]
    fn test_path_graph() {
        let adj = vec![
            vec![0, 1, 0, 0],
            vec![1, 0, 1, 0],
            vec![0, 1, 0, 1],
            vec![0, 0, 1, 0],
        ];
        let path = hamiltonian_path(&adj).unwrap();
        assert_eq!(path.len(), 4);
    }

    #[test]
    fn test_any_start() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 1],
            vec![1, 1, 0, 1],
            vec![1, 1, 1, 0],
        ];
        assert!(hamiltonian_path_any(&adj).is_some());
    }

    #[test]
    fn test_bitmask_dp() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 1],
            vec![1, 1, 0, 1],
            vec![1, 1, 1, 0],
        ];
        assert!(hamiltonian_exists_dp(&adj));

        // Disconnected graph
        let adj2 = vec![vec![0, 0, 0], vec![0, 0, 0], vec![0, 0, 0]];
        assert!(!hamiltonian_exists_dp(&adj2));
    }
}

(* 1070: Hamiltonian Path — Backtracking *)

(* Approach 1: Adjacency matrix backtracking *)
let hamiltonian_path adj =
  let n = Array.length adj in
  let path = Array.make n (-1) in
  let visited = Array.make n false in
  path.(0) <- 0;
  visited.(0) <- true;
  let rec solve pos =
    if pos = n then true
    else begin
      let found = ref false in
      for v = 0 to n - 1 do
        if not !found && not visited.(v) && adj.(path.(pos - 1)).(v) = 1 then begin
          path.(pos) <- v;
          visited.(v) <- true;
          if solve (pos + 1) then found := true
          else begin
            path.(pos) <- -1;
            visited.(v) <- false
          end
        end
      done;
      !found
    end
  in
  if solve 1 then Some (Array.to_list path) else None

(* Approach 2: Adjacency list *)
let hamiltonian_path_adj adj n =
  let path = Array.make n (-1) in
  let visited = Array.make n false in
  path.(0) <- 0;
  visited.(0) <- true;
  let rec solve pos =
    if pos = n then true
    else begin
      let found = ref false in
      List.iter (fun v ->
        if not !found && not visited.(v) then begin
          path.(pos) <- v;
          visited.(v) <- true;
          if solve (pos + 1) then found := true
          else begin
            path.(pos) <- -1;
            visited.(v) <- false
          end
        end
      ) adj.(path.(pos - 1));
      !found
    end
  in
  if solve 1 then Some (Array.to_list path) else None

(* Approach 3: Try all starting vertices *)
let hamiltonian_path_any adj =
  let n = Array.length adj in
  let path = Array.make n (-1) in
  let visited = Array.make n false in
  let rec solve pos =
    if pos = n then true
    else begin
      let found = ref false in
      for v = 0 to n - 1 do
        if not !found && not visited.(v) && adj.(path.(pos - 1)).(v) = 1 then begin
          path.(pos) <- v;
          visited.(v) <- true;
          if solve (pos + 1) then found := true
          else begin
            path.(pos) <- -1;
            visited.(v) <- false
          end
        end
      done;
      !found
    end
  in
  let result = ref None in
  for start = 0 to n - 1 do
    if !result = None then begin
      Array.fill path 0 n (-1);
      Array.fill visited 0 n false;
      path.(0) <- start;
      visited.(start) <- true;
      if solve 1 then result := Some (Array.to_list path)
    end
  done;
  !result

let () =
  (* Complete graph K4 — trivially has Hamiltonian path *)
  let adj = [|
    [|0;1;1;1|];
    [|1;0;1;1|];
    [|1;1;0;1|];
    [|1;1;1;0|]
  |] in
  (match hamiltonian_path adj with
   | Some path -> assert (List.length path = 4)
   | None -> assert false);

  (* Path graph: 0-1-2-3 *)
  let adj2 = [|
    [|0;1;0;0|];
    [|1;0;1;0|];
    [|0;1;0;1|];
    [|0;0;1;0|]
  |] in
  (match hamiltonian_path adj2 with
   | Some path -> assert (List.length path = 4)
   | None -> assert false);

  (match hamiltonian_path_any adj with
   | Some path -> assert (List.length path = 4)
   | None -> assert false);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_complete_graph() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 1],
            vec![1, 1, 0, 1],
            vec![1, 1, 1, 0],
        ];
        let path = hamiltonian_path(&adj).unwrap();
        assert_eq!(path.len(), 4);
    }

    #[test]
    fn test_path_graph() {
        let adj = vec![
            vec![0, 1, 0, 0],
            vec![1, 0, 1, 0],
            vec![0, 1, 0, 1],
            vec![0, 0, 1, 0],
        ];
        let path = hamiltonian_path(&adj).unwrap();
        assert_eq!(path.len(), 4);
    }

    #[test]
    fn test_any_start() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 1],
            vec![1, 1, 0, 1],
            vec![1, 1, 1, 0],
        ];
        assert!(hamiltonian_path_any(&adj).is_some());
    }

    #[test]
    fn test_bitmask_dp() {
        let adj = vec![
            vec![0, 1, 1, 1],
            vec![1, 0, 1, 1],
            vec![1, 1, 0, 1],
            vec![1, 1, 1, 0],
        ];
        assert!(hamiltonian_exists_dp(&adj));

        // Disconnected graph
        let adj2 = vec![vec![0, 0, 0], vec![0, 0, 0], vec![0, 0, 0]];
        assert!(!hamiltonian_exists_dp(&adj2));
    }
}

Deep Comparison

Hamiltonian Path — Comparison

Core Insight

Finding a Hamiltonian path is NP-complete. Backtracking explores all orderings; bitmask DP (Held-Karp style) checks existence in O(2^n × n^2). The bitmask approach represents visited-node sets as integers, enabling efficient DP.

OCaml Approach

• Array.fill for resetting path/visited between start vertices

• ref flag for early exit in inner loop

• Array.to_list for result conversion

• No bitmask DP shown (less natural in OCaml)

Rust Approach

• vec![false; n] for visited tracking

• Inner fn with explicit mutable references

• Bitmask DP: vec![vec![false; n]; 1 << n] — 2D table indexed by (mask, node)

• (0..n).any() for checking if any ending node reaches full mask

Comparison Table

Aspect	OCaml	Rust
Reset arrays	`Array.fill path 0 n (-1)`	Recreate `vec![0; n]` per start
Bitmask DP	Not idiomatic	`1 << n` + bitwise ops — natural
Early exit	`ref` flag	`return true`
Complexity	O(n!) backtracking	O(2^n × n^2) bitmask DP
Path reconstruction	`Array.to_list`	Return `Vec<usize>` directly

Exercises

Implement hamiltonian_circuit that additionally requires the last vertex to be adjacent to the first (completing the cycle).

Add the bitmask DP optimization for graphs up to 20 vertices: dp[mask][v] = true if the subset encoded by mask has a Hamiltonian path ending at vertex v.

Write tsp_exact(dist: &Vec<Vec<f64>>) -> (f64, Vec<usize>) using Held-Karp DP for the minimum-cost Hamiltonian circuit.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust